In consideration of modern architectures and memory layout, are linked data structures ever worth it?
It feels like an dynamic array is a lot better in every sense.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 0:19
>>7
Arrays and Multi-Dimensional arrays. If you want to know how i do something in O(1) time just ask. I never had problems with array speed since i started and i never had the need to use or invent something faster.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 0:27
Deleting Array elements:I just put NULL values for the datatype O(1) here
Adding array space: realloc or making array with some MAX_SIZE which should be enough for most things. O(1)
Indexing: accessing the element[number] O(1)
Modifying Array Cells:one instant operation array[element]=value: O(1)
Anything else?
Name:
Anonymous2011-12-13 0:45
>>14 Deleting Array elements:I just put NULL values for the datatype O(1) here
that's not how a delete function in a dynamic array works. You do know what a dynamic array is, right? Adding array space: realloc or making array with some MAX_SIZE which should be enough for most things. O(1)
wasting space, why am i not surprised you bloat your own programs. realloc O(1)
more proof you're retarded
Name:
Anonymous2011-12-13 0:51
>>14
How's that O(1) search function coming along with your shitty arrays?
>>17
It's not boring—it doesn't even work! How can it be boring if it's broken‽ Laziness is a virtue in programming, but no worries, this kind of code will provide you with plenty of mop-up work to do.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 2:10
>>16
I use binary search on sorted arrays if its required, and i don't insert stuff inside the array, i find empty slots first(since the MAX_SIZE array has empty slots at the end)
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 2:15
Insert into array is 2 stage operation:
1.find first empty/deleted slot(fileld with NULL values)
2.overwrite it with your value
the #1 is stored for convenience as extra variable describing where to get storage without searching empty slots each time.
the #2 is O(1) operation
=======================
Search for some value is not often needed: i usually prefer to store such "key values" in their own variables.
In case you need fast search:
1.sort the array. Should be pre-sorted if you want maximum speed.
2.binary search the array. O(Log N) at worst case O(1) at best
Name:
Anonymous2011-12-13 2:36
>> 20 1.find first empty/deleted slot(fileld with NULL values)
O(n)
the #1 is stored for convenience as extra variable describing where to get storage without searching empty slots each time.
Two successive deletions would need more than one variable.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 2:50
>>21
If you use the insert that much you will maintain arrays of EmptySlots filled with N indexes to free array elements.
If you use Insert rarely you will maintain one variable and update it after each insert.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 2:58
I don't normally need any empty slots, since i design the program such that i append new values at end of last non-empty element(the real_size of array not allocated_size) which is less then MAX_SIZE(allocated_size),and when array is too fragmented i compactify the empty slots and array first empty element become a lower index with.
Name:
Anonymous2011-12-13 3:07
>>22
Isn't an excuse for this poorly designed “algorithm”.
>>23 when array is too fragmented i compactify the empty slots
How often do you scan the array to know this?
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 3:08
>>24
When Real_size reaches around 10-20 elements below allocated_size.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 3:09
I do not "scan the array" the real_size isincremented by one with each new element, and when the array is compacted i updated the real_size.
Name:
Anonymous2011-12-13 3:19
I always lazily delete from my data structures, it gives me that refreshing Java feel when I waste memory.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 3:23
>>27
Wasting a couple of kilobytes or even megabytes is not that criticial.
You waste far more in CPU time if you keep the array compacted all time.
if you don't care about the ordering of your array, you can delete arbitrary elements from the array by copying the last element of the array to the deletion index, and then decrementing the array size by one. You can reallocate the array to save space if it shrinks too small.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 5:43
The point is you don't delete elements, you NULL them and continue using the array, until you need fresh slots (which are usually from end to allocated_size).
Name:
Anonymous2011-12-13 5:53
>>36
How are you certain that NULL isn't a valid value for an element in the array?
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 5:54
>>37
the ARRAY_NULL is defined as value which is invalid for any element.
Name:
F r o z e n V o i d !!mJCwdV5J0Xy2A212011-12-13 5:54