Data structures Examples
Data Structures and beyond
Igor Petruk
EPAM Systems.
London, 2013
Igor Petruk
Data Structures and beyond
Data structures Examples
Data structures Goals What is a data structure?
Examples
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
Goals of the presentation Find data structures you like (maybe reminds a part of your system)
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
Goals of the presentation Find data structures you like (maybe reminds a part of your system) Make a note with their names
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
Goals of the presentation Find data structures you like (maybe reminds a part of your system) Make a note with their names Become aware of availability of the trickiest data structures
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
Goals of the presentation Find data structures you like (maybe reminds a part of your system) Make a note with their names Become aware of availability of the trickiest data structures Discover some cool ways to use them
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
Goals of the presentation Find data structures you like (maybe reminds a part of your system) Make a note with their names Become aware of availability of the trickiest data structures Discover some cool ways to use them Get inspired to practice data structure driven development
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
Goals of the presentation Find data structures you like (maybe reminds a part of your system) Make a note with their names Become aware of availability of the trickiest data structures Discover some cool ways to use them Get inspired to practice data structure driven development Not a goal of the presentation Trying to remember what I say
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What is a data structure? data structure is a particular way of storing and organizing data in a computer so that it can be used eciently.
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What is a data structure? data structure is a particular way of storing and organizing data in a computer so that it can be used eciently. Built of Data Behaviour
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What is a data structure? data structure is a particular way of storing and organizing data in a computer so that it can be used eciently. Built of Data Behaviour They can
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What is a data structure? data structure is a particular way of storing and organizing data in a computer so that it can be used eciently. Built of Data Behaviour They can Be hard to imagine Be complex to understand Solve your problem in one go
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common?
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable They can be Eager vs Lazy
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable They can be Eager vs Lazy Mutable vs Immutable
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable They can be Eager vs Lazy Mutable vs Immutable Persistent
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable They can be Eager vs Lazy Mutable vs Immutable Persistent Finite vs Innite
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable They can be Eager vs Lazy Mutable vs Immutable Persistent Finite vs Innite
Computed
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable They can be Eager vs Lazy Mutable vs Immutable Persistent Finite vs Innite
Computed
Probabilistic
Igor Petruk
Data Structures and beyond
Data structures Examples
Goals What is a data structure?
What kinds are out there?
Some examples (from Java) HashMap LinkedList Array TreeSet Anything in common? Eager, nite, mutable They can be Eager vs Lazy Mutable vs Immutable Persistent Finite vs Innite
Computed
Probabilistic Optimized for specic environment
On disk
Igor Petruk Data Structures and beyond
Data structures Examples
MultiSet
What is it A set Each value contains a counter
Igor Petruk
Data Structures and beyond
Data structures Examples
MultiSet
What is it A set Each value contains a counter Usage Statistics
Put values in Get element occurence count
Igor Petruk
Data Structures and beyond
Data structures Examples
MultiSet
What is it A set Each value contains a counter Usage Statistics
Put values in Get element occurence count
Save memory
Still using a set
Igor Petruk
Data Structures and beyond
Data structures Examples
MultiSet
What is it A set Each value contains a counter Usage Statistics
Put values in Get element occurence count
Save memory
Still using a set
Uniqueness sanity check
Put values in Filter entries with count>1 Collect your errors
Igor Petruk
Data Structures and beyond
Data structures Examples
MultiSet
What is it A set Each value contains a counter Usage Statistics
Put values in Get element occurence count
Save memory
Still using a set
Uniqueness sanity check
Put values in Filter entries with count>1 Collect your errors
Maintain leaders
Put values in realtime Use max-rst iterator
Igor Petruk
Data Structures and beyond
Data structures Examples
Trie - Prex tree
What is it
Igor Petruk
Data Structures and beyond
Data structures Examples
Trie - Prex tree
Branch keys can be anything String Chars Custom objects Bits
Bit chunks of hash, Hash Array Mapped Trie
Igor Petruk
Data Structures and beyond
Data structures Examples
Trie - Prex tree
Branch keys can be anything String Chars Custom objects Bits
Bit chunks of hash, Hash Array Mapped Trie
Usage As a map
No collisions with linear search in bucket No rebalancing
Igor Petruk
Data Structures and beyond
Data structures Examples
Trie - Prex tree
Branch keys can be anything String Chars Custom objects Bits
Bit chunks of hash, Hash Array Mapped Trie
Usage As a map
No collisions with linear search in bucket No rebalancing
Prex search
Best support for this operation
Igor Petruk
Data Structures and beyond
Data structures Examples
Trie - Prex tree
Branch keys can be anything String Chars Custom objects Bits
Bit chunks of hash, Hash Array Mapped Trie
Usage As a map
No collisions with linear search in bucket No rebalancing
Prex search
Best support for this operation
Compression
If prexes are shared
Igor Petruk
Data Structures and beyond
Data structures Examples
Trie - Prex tree
Branch keys can be anything String Chars Custom objects Bits
Bit chunks of hash, Hash Array Mapped Trie
Usage As a map
No collisions with linear search in bucket No rebalancing
Prex search
Best support for this operation
Compression
If prexes are shared
Indexing, Full Text Search
Sux Trie
Igor Petruk Data Structures and beyond
Data structures Examples
Splay tree
Splay tree Balances in order last access rst
Igor Petruk
Data Structures and beyond
Data structures Examples
Splay tree
Splay tree Balances in order last access rst
Usage LRU Cache
Igor Petruk
Data Structures and beyond
Data structures Examples
Splay tree
Splay tree Balances in order last access rst
Usage LRU Cache Why not to talk about cache in general?
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Cache Cache is not a BIG THING Caches that are as lightweight and simple as a map are available (Guava)
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Cache Cache is not a BIG THING Caches that are as lightweight and simple as a map are available (Guava) Data Simple trees, splay trees Databases Files O-heap
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Behaviour Population strategy
Manual Loading
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Behaviour Population strategy
Manual Loading
Write strategy
Read-only Write through Write behind
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Behaviour Population strategy
Manual Loading
Write strategy
Read-only Write through Write behind
Eviction strategy
LRU MRU LFU Random Garbage collector driven Multi Queue
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Complex?
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Complex? LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder() .maximumSize(1000) .expireAfterWrite(10, TimeUnit.MINUTES) . build( new CacheLoader<Key, Graph>() { public Graph load(Key key) throws AnyException { return createExpensiveGraph(key); } });
Igor Petruk
Data Structures and beyond
Data structures Examples
Cache
Usage other then obvious Protecting against eventual consistency issues Batching Memoization Dynamic programming Concurrent synchronization
Igor Petruk
Data Structures and beyond
Data structures Examples
View
View Is this a data structure? YES/NO
Igor Petruk
Data Structures and beyond
Data structures Examples
View
View Is this a data structure? YES/NO We have the data (somewhere) We have the behaviour Why copy?
Igor Petruk
Data Structures and beyond
Data structures Examples
View
Usage See a list as a map
Igor Petruk
Data Structures and beyond
Data structures Examples
View
Usage See a list as a map Process only needed part of data
Igor Petruk
Data Structures and beyond
Data structures Examples
View
Usage See a list as a map Process only needed part of data Perform multiple operations together
Each operation produces a wrapper Final operation - copy
Igor Petruk
Data Structures and beyond
Data structures Examples
View
Usage See a list as a map Process only needed part of data Perform multiple operations together
Each operation produces a wrapper Final operation - copy
Does anyone know how to concat two immutable lists with O(1) complexity?
Igor Petruk
Data Structures and beyond
Data structures Examples
View
Usage See a list as a map Process only needed part of data Perform multiple operations together
Each operation produces a wrapper Final operation - copy
Does anyone know how to concat two immutable lists with O(1) complexity?
Combine data structures
Igor Petruk
Data Structures and beyond
Data structures Examples
View
Usage See a list as a map Process only needed part of data Perform multiple operations together
Each operation produces a wrapper Final operation - copy
Does anyone know how to concat two immutable lists with O(1) complexity?
Combine data structures
Use listeners to build change aware view
Indexing Live display Reactive programming
Igor Petruk
Data Structures and beyond
Data structures Examples
Persistent data structures
Persistent data structures Any mutation produces new version of a structure Previous version remains unless deleted (or garbage collected) Usually designed to reuse most of the previous version
Igor Petruk
Data Structures and beyond
Data structures Examples
Persistent data structures
Persistent data structures Any mutation produces new version of a structure Previous version remains unless deleted (or garbage collected) Usually designed to reuse most of the previous version Examples Immutable linked list (cons list) Immutable trees Usually immutable functional data structure are persistent
Igor Petruk
Data Structures and beyond
Data structures Examples
Persistent data structures
Persistent data structures Any mutation produces new version of a structure Previous version remains unless deleted (or garbage collected) Usually designed to reuse most of the previous version Examples Immutable linked list (cons list) Immutable trees Usually immutable functional data structure are persistent Usage When we have a single writer - they are lock free
Igor Petruk
Data Structures and beyond
Data structures Examples
Persistent data structures
Persistent data structures Any mutation produces new version of a structure Previous version remains unless deleted (or garbage collected) Usually designed to reuse most of the previous version Examples Immutable linked list (cons list) Immutable trees Usually immutable functional data structure are persistent Usage When we have a single writer - they are lock free Any instance of PDS is a snapshot already
Igor Petruk
Data Structures and beyond
Data structures Examples
Persistent data structures
Persistent data structures Any mutation produces new version of a structure Previous version remains unless deleted (or garbage collected) Usually designed to reuse most of the previous version Examples Immutable linked list (cons list) Immutable trees Usually immutable functional data structure are persistent Usage When we have a single writer - they are lock free Any instance of PDS is a snapshot already Put a journal in front of writer, store PDS to disk sometimes and here it goes - durable high performance in-memory database with O(1) snapshot support
Igor Petruk Data Structures and beyond
Data structures Examples
Bloom lter
Bloom lter A probabilistic set Can represent set of elements from innite universe
Igor Petruk
Data Structures and beyond
Data structures Examples
Bloom lter
Bloom lter A probabilistic set Can represent set of elements from innite universe Strict test if the set does NOT contain the element
Igor Petruk
Data Structures and beyond
Data structures Examples
Bloom lter
Bloom lter A probabilistic set Can represent set of elements from innite universe Strict test if the set does NOT contain the element Probabilistic test if the set contains the element
Igor Petruk
Data Structures and beyond
Data structures Examples
Bloom lter
Bloom lter A probabilistic set Can represent set of elements from innite universe Strict test if the set does NOT contain the element Probabilistic test if the set contains the element Internals An array of m bits k dierent hash functions, that produce values from 0 to m-1 Extendable to counting Bloom lter which supports deletion
Igor Petruk
Data Structures and beyond
Data structures Examples
Bloom lter
Bloom lter A probabilistic set Can represent set of elements from innite universe Strict test if the set does NOT contain the element Probabilistic test if the set contains the element Internals An array of m bits k dierent hash functions, that produce values from 0 to m-1 Extendable to counting Bloom lter which supports deletion Notable usages Apache Cassandra and Google BigTable
Test if the record can be on the disk If it can - fetch it from the disk If not, then we dont have to trigger a disk operation
Igor Petruk Data Structures and beyond
Data structures Examples
Stream
Stream List Evaluator in tail Can be innite
Igor Petruk
Data Structures and beyond
Data structures Examples
Stream
Stream List Evaluator in tail Can be innite Usage Good abstraction for innite computation that can be consumed by list processing routines
Igor Petruk
Data Structures and beyond
Data structures Examples
Stream
Stream List Evaluator in tail Can be innite Usage Good abstraction for innite computation that can be consumed by list processing routines If internal list is a linked list, then the GC can gather already processed data
Igor Petruk
Data Structures and beyond
Data structures Examples
Stream
Stream List Evaluator in tail Can be innite Usage Good abstraction for innite computation that can be consumed by list processing routines If internal list is a linked list, then the GC can gather already processed data Change denition of int b(int) to Stream<Integer> b()
Igor Petruk
Data Structures and beyond
Data structures Examples
Stream
Stream List Evaluator in tail Can be innite Usage Good abstraction for innite computation that can be consumed by list processing routines If internal list is a linked list, then the GC can gather already processed data Change denition of int b(int) to Stream<Integer> b() You still can represent input, but via generic Stream
Igor Petruk
Data Structures and beyond
Data structures Examples
Stream
Stream List Evaluator in tail Can be innite Usage Good abstraction for innite computation that can be consumed by list processing routines If internal list is a linked list, then the GC can gather already processed data Change denition of int b(int) to Stream<Integer> b() You still can represent input, but via generic Stream Convert one stream to another via wrappers
Igor Petruk
Data Structures and beyond
Data structures Examples
Option
Option One or zero element collection
Igor Petruk
Data Structures and beyond
Data structures Examples
Option
Option One or zero element collection Null is no more! JK, easy conversion from null to Option and back
Igor Petruk
Data Structures and beyond
Data structures Examples
Option
Option One or zero element collection Null is no more! JK, easy conversion from null to Option and back Forces you to unbox the value before usage Usage
Igor Petruk
Data Structures and beyond
Data structures Examples
Option
Option One or zero element collection Null is no more! JK, easy conversion from null to Option and back Forces you to unbox the value before usage Usage Do you have and element or not? Is the computation sucessful or not? Is the value populated or not by user? Null safe operations within Option Available in Guava as Optional Monad
Igor Petruk
Data Structures and beyond
