Opened 9 years ago

Last modified 5 years ago

#674 confirmed task

Use binary search instead of iteration in alloc tables

Reported by: takkaria Owned by:
Milestone: Future Keywords: items
Cc:

Description (last modified by takkaria)

Instead of iterating over every entry in an alloc table to find an item and keeping a cumulative tally while iterating, store the total in the alloc tables and use a binary search to find it. e.g. instead of

alloc[0] = { item 1, entries 50 }
alloc[1] = { item 2, entries 100 }
alloc[2] = { item 5, entries 30 }

have

alloc[0] = { item 1, entries 0 }
alloc[1] = { item 2, entries 50 }
alloc[2] = { item 5, entries 150 }

Change History (8)

comment:1 Changed 9 years ago by takkaria

  • Milestone changed from 3.1.1 beta to 3.1.2 beta

comment:2 Changed 8 years ago by magnate

  • Keywords items added

comment:3 Changed 7 years ago by magnate

  • Milestone changed from 3.2.0 to 3.3.0

Punting to 3.3: non-urgent bug or change.

comment:4 Changed 7 years ago by magnate

  • Type changed from change to task

comment:5 Changed 6 years ago by magnate

  • Milestone changed from 3.3.0 to Future
  • Status changed from new to confirmed

Punting in accordance with new milestone policy (that any other milestone is only set once someone is actually working on the ticket).

comment:6 Changed 6 years ago by magnate

I've just read this ticket properly for the first time. Isn't this what the object_alloc table does?

comment:7 Changed 6 years ago by takkaria

No, it doesn't use a binary search.

comment:8 Changed 5 years ago by takkaria

  • Description modified (diff)
  • Summary changed from Speed up item generation to Use binary search instead of iteration in alloc tables
Note: See TracTickets for help on using tickets.