Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

Temporal data [was is REBOL OO]

 [1/8] from: SunandaDH::aol::com at: 12-Jan-2004 17:39


HI Gerard,
> Just to give you an idea of the involved difficulties, imagine > a customer that phones at the arena and want to know if
<<quoted lines omitted: 7>>
> the other end of the phone. > I know how real and good is the efficiency of the paper method in such a
case
> but I always dreamed of some tool to explore with a > computer. I think REBOL could be this tool - if we could get some way to > connect it to some external way to enter data like a touch > screen can do instead of a mouse and a keyboard. In fact the three should > intermixed in this app.
I once knew someone who was charged a small fortune for a computer system to do precisely that. Absolutely crazy. Nothing could beat their two-stage wall chart: pencilled in for provisional bookings, inked in when confirmed. On the other hand, it doesn't scale well. I've worked on realtime reservations systems. Before airlines had computers, they had large warehouses full of telephone order takers (a 1950s call center). Flight details were marked on blackboards around the walls. Runners (the younger kids) ran back and forth updating the boards as flight details (e.g. seating capacity) changed. At one point, the airlines were the binocular manufacturer's biggest customers. (You are sitting at a phone at one end of a warehouse. How else do you read a blackboard at the far end?) The sort of data structures you need for handling the sale of time (as opposed to material goods) are fairly non-intuitive if you've never worked in that area. Read up on "temporal databases" if you want an insight into a whole new world, and possibly a few headaches. The other thing that is vital with this sort of application is not just availability checking (have we got what they've asked for?) but also the automatic offering of alternatives. In your example, the system should automatically offer these sorts of alternatives (assuming they are available) and sequence them in a blend of the customer's priorities (wednesdays are nice, but evenings are essential) and the company's yield management goals (we gotta take some afternoon bookings soon!) -- 11 consecutive weds plus 1 after a gap over Thanksgiving weekend. -- 12 consecutive thursdays starting 3 weeks after their desired date -- 10 consecutive wednesdays late afternoons -- 6 weeks here and 6 weeks at our sister site ten blocks away. To rummage a database realtime for those sorts of alternatives can be very processor heavy. Example, suppose I wanted any 5 consecutive slots, any time of day, in the six months, ordered by lowest booking price, if I was to pay by next Tuesday -- remember your pricing may vary by the week (xmas is higher) and you may have specials if I book by a given date). At a quick glance, that looks like you have to run through almost every combination of slots that are available, and price them. Getting performance for something like that is a real pig. That's why real airlines (until perhaps very recently) don't use real databases. No one's got time for record locking and transaction rollback features and stuff like that. Not when you want to do 200 vague queries like the one above per a second across a multi-terabyte database that is being simultaneously bulk loaded with next year's flight inventory. If that doesn't scare you off, then I do have in my head a design for such a system (though not so high performance) using REBOL and (if we have to -- but I'd rather not) a standard SQL database for the raw user data. It's been on the backburner for the past year or so, as the people who want it are nothing like ready. There is a chance it might be a goer later this year. But I'm still fairly agnostic about whether REBOL is a great tool for this. Sunanda.<

 [2/8] from: gerardcote:sympatico:ca at: 12-Jan-2004 20:51


Hi Sunanda, you wrote this : ==========
> The other thing that is vital with this sort of application is not just > availability checking (have we got what they've asked for?) but also the automatic
<<quoted lines omitted: 7>>
> -- 10 consecutive wednesdays late afternoons > -- 6 weeks here and 6 weeks at our sister site ten blocks away.
I'm glad someone here on the ML has already had sufficient experience in th epast with that kind of reservation system so that he is able to complete what was coming before I had to complete myself the example. In fact you are absolutely right when you say that the next step is to offer some alternatives to the customer that are based upon his own priorities (which are generally not known before the CALL had been placed to the clerk. This is exactly what the reality is for this system too. Sometime a client prefer to keep one tuesday p.m. while on another time he will prefer to advance all the reservations one hour sooner or he will prefer to move all wednesdays for thursdays but keep them at 8 p.m. It's similar in all points to what you exposed above and this is why I really thiunk that the humain brain is really enjoying many advantages over a computer system when it comes to express and analyse in real-time what these constraints are. a simple exchange with the clerk by phone and the 2 can agree with some proposed adjustment without having to bother with keyboarding the alternatives or priorities. And the best part is no more training costs and delays for such a manual system - everybody has used some pencil and paper in the past. But I would have liked to try it even though if it is not manageable at all - for fun and learning.
> If that doesn't scare you off, then I do have in my head a design for such a > system (though not so high performance) using REBOL and (if we have to -- but > I'd rather not) a standard SQL database for the raw user data. It's been on > the backburner for the past year or so, as the people who want it are nothing > like ready. There is a chance it might be a goer later this year. > > But I'm still fairly agnostic about whether REBOL is a great tool for this. >
I'm interested to look at this beast if I really get an eye on it but it will also take much time before I would be ready to analyse the way it is really functioning I think. Nevertheless my needs will never be those of the Flights reservation system since a skating is opened only between 6:00 and 23:59 at one hour interval and there is only very few other apps running on this computer at a given time - the most demanding being Excel or Word during tests and after it would be ported on a dedicated computer for enabling this job. At least it is what that was planned until the manager decided that the proposed system would not scale either ;-) and kept the paper and pencil. He simply posts his entries in a deferred manner into the agenda after the verbal exchange took place with his client. And it will be so until I can prove him that is not the best way to do. Never I will try to prove anything like that because I know the real "complexity" inherent with the fact that this task must be accomplished in real-time even during the exchange with the customer and this is not what the computer is good for at this moment. I really appreciate your comment and if you feel like you could let me see the state of your work I would be grateful for too. But I will not either be furious against you if you don't because I know what sum of work it represents. In all cases, Thank you for listening and posting. Regards, Gerard

 [3/8] from: SunandaDH:aol at: 14-Jan-2004 5:15


Hi Gerard: For those of you reading this with no interest in the issues involved in designing realtime reservations systems, here's a couple of related REBOL puzzles -- and I really would like the answers to these; they'd make building such a system in REBOL so much easier -- see last couple of paragraphs of this email. Puzzle 1 We have a bitmap, where each 1-bit represents the availability of a resource on a given day, eg random/seed: 100 data: copy [] loop 200 [ append data to char! random 255 ] bit-map: charset data What we need is the location of the first occurrence of n consecutive 1-bits: available? bit-map 5 available? bit-map 12 Puzzle 2: 256 bits isn't enough for a bit-per-day for a whole year. We need two bitmaps. Extend available? to find n consecutive bits within a bitset, or across a bitset boundaries: bit-map1: charset data bit-map2: charset skip data random 50 available? [bit-map1 bit-map2] 5 available? [bit-map1 bit-map2] 12
> I really appreciate your comment and if you feel like you could let me see > the state of your work > I would be grateful for too. But I will not either be furious against you
if
> you don't because I know what sum of work it > represents.
The state of my work is an in-brain design for a system way larger than the one you want. But here are some ideas, some of which may be relevant.... SEE IF IT WORKS ANYWAY You may well find that you can do what you want with standard software -- in which case you don't have a problem except for scaling as your client grows into a premier nation-wide business. MACHINES, LOTS OF THEM You might just be able to throw hardware at the problem. A dozen USD300 Linux boxes from Walmart each running part of the availability search may solve the problem. STANDARD DATA WAREHOUSE An off-the-shelf data warehouse package may work for you. Data warehousing is designed to take large lumps of data, reduce it down in ways that make it extremely easy to sort and sift and analyse, but a total pig if you ever needed to update it. Most data warehousing users throw all their historical data into the warehouse every few months or so, so dating happens rarely. A reservations system, in effect, uses data warehouse techniques for fast searching, but on an availability database that gets rebuilt every day. That means most queries are in two parts: 1. Query the availability database for a list of alternatives 2. Check those against the actual inventory to see if they are still available. You can probably see one obvious flaw in that -- if a booking is cancelled, the stock won't show up in the availability database until it is rebuilt. So, for the rest of that day (or until the availability database is rebuilt) that item can't be found in searches, and so a sale may be lost. That may not matter too much for a flight that happens in three months -- there is still plenty of time to sell it before departure time. But it could be lost revenue if the flight goes today. That's why: 1. cancellation charges are so high close to departure date 2. Look at most holiday/reservations systems on the web. They almost all have a "Last minute" or "late bargains" or some such search feature. Why? Because those searches run in a completely different way -- either against the live inventory data, or against another specialised search database. BUILD YOUR OWN SEARCH DATABASE If off-the-shelf warehousing is too slow for real-time queries (or it takes too long to rebuild the database each day), then think about building your own. The main things to do are to reduce data down as small as possible into data structures that you can search very fast. And are carefully constructed to handle the typical queries the system expects. One method is to use bit-maps -- hence the opening puzzle. If, say, you have one bit-map for "10pm-11pm Singles Special" with a bit set for each day of the year that is available, and another bit-map for "Senior discount days" for the days when you offer reduced entry to seniors, then answering the question... I'm a senior: do you have any weekend singles specials at a discount for me? ...is pretty trivial -- assuming, of course, you are using a language that can dice and slice and rifflle shuffle long strings of bits. Which is why I wrote: <<But I'm still fairly agnostic about whether REBOL is a great tool for this.>> Sunanda.<

 [4/8] from: g:santilli:tiscalinet:it at: 14-Jan-2004 14:09


Hi SunandaDH, On Wednesday, January 14, 2004, 11:15:52 AM, you wrote: Sac> What we need is the location of the first occurrence of n consecutive 1-bits: Sac> available? bit-map 5 Sac> available? bit-map 12 Sac> Puzzle 2: Sac> 256 bits isn't enough for a bit-per-day for a whole year. We need two Sac> bitmaps. Sac> Extend available? to find n consecutive bits within a bitset, or across a Sac> bitset boundaries: Well, since we're talking 356 bits, maybe you'll forgive me wasting some memory.
>> bitmap: "000110101000111111100101001111111" ;... till 356 days
== "000110101000111111100101001111111"
>> available?: func [bitmap cons] [if bitmap: find bitmap head insert/dup clear "" 1 cons [index? bitmap]] >> available? bitmap 1
== 4
>> available? bitmap 2
== 4
>> available? bitmap 3
== 13
>> available? bitmap 5
== 13 Regards, Gabriele. -- Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer Amiga Group Italia sez. L'Aquila --- SOON: http://www.rebol.it/

 [5/8] from: SunandaDH:aol at: 14-Jan-2004 13:21


Hi Gabriele,
> Well, since we're talking 356 bits, maybe you'll forgive me > wasting some memory. > > >> bitmap: "000110101000111111100101001111111" ;... till 356 days > == "000110101000111111100101001111111" > >> available?: func [bitmap cons] [if bitmap: find bitmap head insert/dup > clear "" 1 cons [index? bitmap]]
Thanks for the reply. That's a neat bit of lateral thinking! You correctly spotted that Puzzle 2 was a trick question to highlight the inadequacies of using REBOL's bitmaps for binary strings longer than 32 octets -- so that some other sort of representation was needed. A "character bitmap" (to coin a term) of the sort you use, obviously lifts a binary string into a realm in which various standard REBOL operations are possible -- like finding the longest sequence of 1s, reversing the string etc. And it makes possible things that REBOL doesn't properly support like shift/left or rotate/right But it makes it much harder (I won't say impossible, or someone will email in a char-xor function) to do boolean operations. I guess a system that needs to do basic boolean operations on binary strings could do those directly, and then unfurl (to coin another term) the binary string into a character bitmap for those other operations. Provided furling and unfurling was fast, it could work. Ideally, though, REBOL would provide a wider ranger of ways to work with bits. (Another alternative is to write the operations in C or asm and use /Pro or /command. But that makes portability a pain) Thanks again, Sunanda.<

 [6/8] from: greggirwin:mindspring at: 14-Jan-2004 13:25


Sunanda et al Sac> 256 bits isn't enough for a bit-per-day for a whole year. We need Sac> two bitmaps. You can do it with one. bitset: make bitset! 368 loop 200 [insert bitset random 367] s: copy "" repeat i 368 [append s to integer! find bitset i - 1] print s available?: func [bitset len] [ mark: 1 count: 0 repeat i subtract length? bitset 1 [ either find bitset i [ count: count + 1 if count >= len [return mark] ][mark: i + 2 count: 0] ; The + 2 accounts for bitsets having a 0 base ; and the mark being set to the next bit. ] ] repeat i 6 [print available? bitset i] -- Gregg

 [7/8] from: SunandaDH:aol at: 14-Jan-2004 17:15


Hi Gregg!
> Sac> 256 bits isn't enough for a bit-per-day for a whole year. We need > Sac> two bitmaps. > > You can do it with one.
Amazing, thanks. I think I'd got myself blindsided about the maximum length of a bitset because of the length of a charset charset. I should have remembered that Carl is subtler than most of my assumptions. Incidentally, I thought I was about to find a bug in your code, or in the way bits are inserted in bitsets. Consider this: mybitset: make bitset 128 insert mybitset 7 insert mybitset 8 mold mybitset "make bitset! #{80010000000000000000000000000000}" Look at that: those two bits are nowhere near adjacent. But: available? mybitset 2 == 8 Correct answer! Must be an endian issue in the way bitsets are displayed. Bits in an octet are numbered left to right (from 0 to 7, natch) but displayed right to left, thus creating an optical illusion that bits 0 and 15 are adjacent:
>> mybitset: make bitset 16
== make bitset! #{0000}
>> insert mybitset 0
== make bitset! #{0100}
>> insert mybitset 15
== make bitset! #{0180} Just another of those REBOL gotchas. Sunanda.

 [8/8] from: g:santilli:tiscalinet:it at: 15-Jan-2004 10:01


Hi SunandaDH, On Wednesday, January 14, 2004, 7:21:39 PM, you wrote: Sac> But it makes it much harder (I won't say impossible, or someone will email in Sac> a char-xor function) to do boolean operations. You could use a binary! and use the characters #{00} and #{01}; then you can easily use boolean operations. This is still somewhat a waste of memory, but as long as we're talking a couple thousand chars noone would really notice it. :)
>> #{0001010100} xor #{0101000000}
== #{0100010100} Regards, Gabriele. -- Gabriele Santilli <[g--santilli--tiscalinet--it]> -- REBOL Programmer Amiga Group Italia sez. L'Aquila --- SOON: http://www.rebol.it/

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted