1) The programming language has a main built-in data type called list, used as such: l = [1,2,3];. What would you normally expect of the underlying implementation -- would you expect it to be a linked-list (random access O(N)), an array (resize O(N)), or perhaps an unrolled link list (random access and resize amortized O(log(N)))?
2) You discover that the programming language also has a built-in data type called array. How does this affect your assumptions relative to list, and what will your new expectancies relative to array be?
keying by numbers is rarely useful in practice. Use of arrays over linked list is interesting only as an optimization, and at worst indicates imperative side-effect-ful AIDS
Name:
Anonymous2011-09-26 22:16
1) I would not think about it
2) I would assume that one was an array and the other a linked list.
>>11
Go back to your Blub code, plumber. In good software a B-tree node has a linked list of children, a hash table has a linked list of buckets, and main memory is a linked list of bytes.
rpetual statute: and thou shalt consecrate Aaron and his sons.
29:10 And thou shalt cause a bullock to be brought before the
tabernacle of the congregation: and Aaron and his sons shall put their
hands upon the head of the bullock.
29:11 And thou shalt kill the bullock before the LORD, by the door of
the tabernacle of the congregation.
29:12 And thou shalt take of the blood of the bullock, and put it upon
the horns of the altar with thy finger, and pour all the blood beside
the bottom of the
Name:
Anonymous2011-09-27 3:52
>a linked list of bytes.
Why not a linked list of bits? Should be more type-agnostic, and homoiconic without those pesky hardware differences.
Name:
Anonymous2011-09-27 3:58
I had
U1
U2
U4
U8
F8
nice two column for unassembly and stuff
got sick of the confusion.
Name:
Anonymous2011-09-27 4:05
You would think people would understand it was bytes, not bits from usage. Nope. Everybody thought ARM or something.
I have learned just how easy it is to confuse people in so many ways. They are sheeple.
Name:
Anonymous2011-09-27 4:08
If it's in memory, not on disk. Hash tables should be linked-lists. Never have to worry about filling-up and you allocate pointers in the table, not entries!
On disk, it can be okay to have cponventional hash tables.
If you try implementing a hash table both ways in memory, you'll never go back to conventional ones because they're retarded.
Name:
Anonymous2011-09-27 4:10
I sort-of independently reinvented linked-list hash tables. The conventional ones are so so stupid!
Unless its an array of bytes, that would be perfectly sensible..
Name:
Anonymous2011-09-27 7:36
C-like structures, dynamic arrays, non-generic hash tables, and cons cells are all you need. Common Lisp did it right.
Unrolled linked lists are a hoax and other generic data structures are bad. The STL especially is a crime against humanity.
>>23
Cons cells implemented as simple linked lists on top of a naïve memory pool allocator (that obviously doesn't care about cache locality) are great way to load useless shit into most of your cache. I can't see how you can possibly think that linked lists are a better idea than unrolled linked lists, unless of course you're writing most of your Common Lisp code imperatively, in which case you should be taken outside to the parking lot and shot.
[]non-generic[/b] hash tables
You mean the ones where you can't supply your own comparator function so it uses the reference casted to an integer as a key? Yeah, no, no thanks.
other generic data structures are bad
A language whose standard library doesn't supply a B-heap or B-tree data structure isn't worth its salt.
The STL especially is a crime against humanity.
I agree, but we're talking about decent languages here, which excludes C++.
Name:
Anonymous2011-09-27 9:27
They're the same
List is an array optimized for fixed-length use. You need to use list operators on it, while incrementing it increases all the cells value by 1,etc.
The array function would be such that if you incremented it, it would increase the memory cells. You are required to access a cell before modifying it, there is no operator overloading bullshit.
Name:
Anonymous2011-09-27 9:32
>>26 I can't see how you can possibly think that linked lists are a better idea than unrolled linked lists
Me neither. But I've yet to see any benchmark proving unrolled linked lists superiority. Also, there's a spirit in the CPU which knows about linked lists.
non-generic hash tables You mean the ones where you can't supply your own comparator function so it uses the reference casted to an integer as a key? Yeah, no, no thanks.
No, I mean that the language has optimized hash tables for its primitive types, but doesn't provide a generic hash table implementation.
>>28 But I've yet to see any benchmark proving unrolled linked lists superiority.
They take less space. Less space means better cache efficiency.
Also, there's a spirit in the CPU which knows about linked lists.
Not convincing.
No, I mean that the language has optimized hash tables for its primitive types, but doesn't provide a generic hash table implementation.
The language shouldn't. But it would be nice if the standard library had one.