Name: Anonymous 2007-12-29 20:59
ok, a question for /prog/rammers:
i need a data structure that can be implemented as a table (or has memory requirement for pointers of less than around 100MiB for 500000000 elements, each of equal size) and has O compexities for inserting and searching through it of less than O(n)?
alternatively has memory requirement of 100MiB for pointers for 500000000 elements of the same size and cannot save multiple occurences of the same data (for example can't save two 1's) and has insertion complexity of less than O(n)
I was thinking about a binary heap, but searching through it is rather slow (isn't it O(n)?)
i implemented a sorted list (in a table), but inserting is awfully slow for more than few MiBs of data (and as the program searches through the data as often as adds new, it's really slow), because inserting has O(n) complexity. (i thought that memmove() will be able to do some wonders and make its use feasible but it didn't work out)
so what will be better?
modified heap (in some way), VList, hashed array tree, else?
tl;dr: data structure with insering complexity less than O(n) and searching also less than O(n) and memory for pointers of O(1) or less than around 100MiB for 500000000 elements
i need a data structure that can be implemented as a table (or has memory requirement for pointers of less than around 100MiB for 500000000 elements, each of equal size) and has O compexities for inserting and searching through it of less than O(n)?
alternatively has memory requirement of 100MiB for pointers for 500000000 elements of the same size and cannot save multiple occurences of the same data (for example can't save two 1's) and has insertion complexity of less than O(n)
I was thinking about a binary heap, but searching through it is rather slow (isn't it O(n)?)
i implemented a sorted list (in a table), but inserting is awfully slow for more than few MiBs of data (and as the program searches through the data as often as adds new, it's really slow), because inserting has O(n) complexity. (i thought that memmove() will be able to do some wonders and make its use feasible but it didn't work out)
so what will be better?
modified heap (in some way), VList, hashed array tree, else?
tl;dr: data structure with insering complexity less than O(n) and searching also less than O(n) and memory for pointers of O(1) or less than around 100MiB for 500000000 elements