jm + arrays   5
interesting new data structure, pending addition in Java 8. Basically an array of arrays which presents the API of a single List.
An ordered collection of elements. Elements can be added, but not removed. Goes through a building phase, during which elements can be added, and a traversal phase, during which elements can be traversed in order but no further modifications are possible.
spinedbuffer  data-structures  algorithms  java  jdk  jvm  java-8  arrays  lists 
october 2013 by jm
Efficient concurrent long set and map
An ordered set and map data structure and algorithm for long keys and values, supporting concurrent reads by multiple threads and updates by a single thread.

Some good stuff in the linked blog posts about Clojure's PersistentHashMap and PersistentVector data structures, too.
arrays  java  tries  data-structures  persistent  clojure  concurrent  set  map 
december 2012 by jm
Special encoding of small aggregate data types in Redis
Nice performance trick in Redis on hash storage:

'In theory in order to guarantee that we perform lookups in constant time (also known as O(1) in big O notation) there is the need to use a data structure with a constant time complexity in the average case, like an hash table. But many times hashes contain just a few fields. When hashes are small we can instead just encode them in an O(N) data structure, like a linear array with length-prefixed key value pairs. Since we do this only when N is small, the amortized time for HGET and HSET commands is still O(1): the hash will be converted into a real hash table as soon as the number of elements it contains will grow too much (you can configure the limit in redis.conf). This does not work well just from the point of view of time complexity, but also from the point of view of constant times, since a linear array of key value pairs happens to play very well with the CPU cache (it has a better cache locality than an hash table).'
memory  redis  performance  big-o  hash-tables  storage  coding  cache  arrays 
november 2012 by jm
AnandTech - The Intel SSD DC S3700: Intel's 3rd Generation Controller Analyzed
Interesting trend; Intel moved from a btree to an array-based data structure for their logical-block address indirection map, in order to reduce worst-case latencies (via Martin Thompson)
latency  intel  via:martin-thompson  optimization  speed  p99  data-structures  arrays  btrees  ssd  hardware 
november 2012 by jm
Open Data Structures
A free-as-in-speech as well as -beer textbook of data structures, covering a great range, including some I hadn't heard of before. Here's the full list: ArrayStack, FastArrayStack, ArrayQueue, ArrayDeque, DualArrayDeque, RootishArrayStack, SLList, DLList,
SEList, SkiplistSSet, SkiplistList, ChainedHashTable, LinearHashTable, BinaryTree, BinarySearchTree, Treap, ScapegoatTree, RedBlackTree, BinaryHeap, MeldableHeap, AdjacencyMatrix, AdjacencyLists, BinaryTrie, XFastTrie, and YFastTrie
algorithms  books  data-structures  computer-science  coding  tries  skiplists  arrays  queues  heap  trees  graphs  hashtables 
may 2012 by jm

Copy this bookmark: