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

Block! v List! dilema...

 [1/4] from: chris:starforge at: 6-Apr-2001 19:09


Hi, Sorry about the waffle, the really important bit is near the end if you're not interested in background detail.. I'm currently working on a project called ROACH (the RebOl Assisted Critter Hunter - a web based bug report and tracking tool. Couldn't resist the acronym). Each ROACH installation can store bugs for a number of projects and each project has its own list of bugs. Bugs can be submitted and commented on by registered users and project admins can alter the status of bugs. If you have ever used a Bulletin Board system like UBB or phpBB you will be familiar with the structure: the front page lists all the projects in the system, selecting a project brings up the list of bugs for that project and clicking on a bug opens the details for the bug. Here's the important bit: the list of bugs for a project is held in a block. The code I use to display the list is: for offset 0 9 1 [ if (start + offset) <= (length? buglist) [ entry: pick buglist (start + offset) ; throw out a table entry to show the bug summary.. ] ] Using a block, I guess that pick for a block is an O(1) operation - a simple array lookup? Now the problem - when a user comments on a bug, or a project admin updates the status of a bug, I want that bug to be moved to the start of the buglist block. Remembering that this list could end up being long (probably into the thousands), removing an element in the middle and inserting it at the start would, I guess, be rather costly. The alternative is to use a list of course: that makes the move very quick, but what does it do to my display code? Is pick for list still O(1) - I guess it isn't? Given that displays vastly outnumber moves, should I just stick with blocks? Or does anyone have a better suggestion? Chris -- New sig in the works Explorer 2260, Designer and Coder http://www.starforge.co.uk -- Never hit a man with glasses. Hit him with a baseball bat.

 [2/4] from: holger:rebol at: 6-Apr-2001 11:52


On Fri, Apr 06, 2001 at 07:09:05PM +0000, Chris wrote:
> Using a block, I guess that pick for a block is an O(1) operation - a > simple array lookup?
Yes.
> Now the problem - when a user comments on a bug, or a > project admin updates the status of a bug, I want that bug to be moved to > the start of the buglist block. Remembering that this list could end up > being long (probably into the thousands), removing an element in the middle > and inserting it at the start would, I guess, be rather costly.
Yes, but it should not be a problem unless you move a large number of elements around in a loop. A single remove/insert only takes a small fraction of a second, even in very large blocks.
> The > alternative is to use a list of course: that makes the move very quick, > but what does it do to my display code? Is pick for list still O(1) - I > guess it isn't?
No, it is O(n).
> Given that displays vastly outnumber moves, should I just stick with blocks? > Or does anyone have a better suggestion?
Blocks are probably better. -- Holger Kruse [holger--rebol--com]

 [3/4] from: chris:starforge at: 6-Apr-2001 20:44


#06-Apr-01# Message from *Holger Kruse*: Hi Holger,
>> Given that displays vastly outnumber moves, should I just stick with >> blocks? Or does anyone have a better suggestion? > Blocks are probably better.
Ok, thanks for the help :) Chris -- New sig in the works Explorer 2260, Designer and Coder http://www.starforge.co.uk -- Good news. Ten weeks from Friday will be a pretty good day.

 [4/4] from: agem:crosswinds at: 7-Apr-2001 1:36


costs of pick, inserting at head and this code: for offset 0 9 1 [ if (start + offset) <= (length? buglist) [ entry: pick buglist (start + offset) ; throw out a table entry to show the bug summary.. ] ] : 1) you work sequentially here? so, why picking? list! should be better in this manner: loop[do-something-with list list: next list] which should be as fast as blocks. like: ;hoping start is very near the buglist-position, otherwise blocks are better list: at buglist start for offset 0 9 1 [ if (start + offset) <= (length? buglist) [ ;not: entry: pick buglist (start + offset) ;but: entry: first list list: next list ; throw out a table entry to show the bug summary.. ] ] 2) list-positions after insertions works a bit different to blocks, you would need some 'head more. usually i find blocks everywhere more surprise-free volker
>>>>>>>>>>>was:
[REBOL] Block! v List! dilema... From: Chris (view other messages by this author) Date: Fri, 6 Apr 2001 12:56:55