sipa changed the topic of #bitcoin-wizards to: This channel is for discussing theoretical ideas with regard to cryptocurrencies, not about short-term Bitcoin development | http://bitcoin.ninja/ | This channel is logged. | For logs and more information, visit http://bitcoin.ninja
chrippa has quit []
jb55 has quit [Remote host closed the connection]
jb55 has joined #bitcoin-wizards
proofofkeags has quit [Remote host closed the connection]
proofofkeags has joined #bitcoin-wizards
proofofkeags has quit [Ping timeout: 260 seconds]
surja795 has joined #bitcoin-wizards
surja795 has quit [Remote host closed the connection]
morcos has quit [Remote host closed the connection]
fkinglag has joined #bitcoin-wizards
morcos has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
regis_ has joined #bitcoin-wizards
nick_freeman has quit [Ping timeout: 260 seconds]
guest534543 has joined #bitcoin-wizards
Kiminuo has quit [Ping timeout: 256 seconds]
guest534543 has quit [Ping timeout: 260 seconds]
votesmith has quit [Quit: bye]
shush has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
shush has quit [Ping timeout: 260 seconds]
nick_freeman has quit [Ping timeout: 256 seconds]
jonatack has quit [Ping timeout: 260 seconds]
jonatack has joined #bitcoin-wizards
dburkett has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
t-bast has joined #bitcoin-wizards
regis_ has quit []
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
BjarniRunar1 has joined #bitcoin-wizards
shesek has quit [Ping timeout: 260 seconds]
dllud has quit [Read error: Connection reset by peer]
dllud has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
TheoStorm has quit [Remote host closed the connection]
TheoStorm has joined #bitcoin-wizards
surja795 has joined #bitcoin-wizards
setpill has joined #bitcoin-wizards
surja795 has quit [Remote host closed the connection]
tromp has quit [Remote host closed the connection]
laptop has joined #bitcoin-wizards
Relis has quit [Quit: This computer has gone to sleep]
CryptoDavid has joined #bitcoin-wizards
jb55 has quit [Remote host closed the connection]
jb55 has joined #bitcoin-wizards
shush has joined #bitcoin-wizards
shush has quit [Ping timeout: 256 seconds]
nick_fre_ has joined #bitcoin-wizards
mryandao has quit [Remote host closed the connection]
nick_freeman has quit [Ping timeout: 260 seconds]
BjarniRunar1 has quit []
likewhoa has quit [Ping timeout: 258 seconds]
likewhoa has joined #bitcoin-wizards
Zenton has quit [Ping timeout: 258 seconds]
zmnscpxj__ has joined #bitcoin-wizards
zmnscpxj_ has quit [Ping timeout: 240 seconds]
Relis has joined #bitcoin-wizards
AbramAdelmo has joined #bitcoin-wizards
Eprom has joined #bitcoin-wizards
Eprom has quit [Ping timeout: 240 seconds]
Zenton has joined #bitcoin-wizards
AbramAdelmo has quit [Ping timeout: 256 seconds]
Chris_Stewart_5 has joined #bitcoin-wizards
zmnscpxj__ has quit [Remote host closed the connection]
zmnscpxj__ has joined #bitcoin-wizards
shush has joined #bitcoin-wizards
shush has quit [Ping timeout: 252 seconds]
dongcarl has joined #bitcoin-wizards
laptop has quit [Ping timeout: 256 seconds]
son0p has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
nick_fre_ has quit [Ping timeout: 260 seconds]
tomkap1 has joined #bitcoin-wizards
nick_freeman has quit [Ping timeout: 252 seconds]
tomkap1 has quit []
nick_freeman has joined #bitcoin-wizards
tromp has joined #bitcoin-wizards
zalun1 has joined #bitcoin-wizards
zalun1 has quit [Client Quit]
tromp has quit [Ping timeout: 246 seconds]
proofofkeags has joined #bitcoin-wizards
jb55 has quit [Read error: Connection reset by peer]
yanmaani has quit [Remote host closed the connection]
ghost43 has quit [Remote host closed the connection]
morcos has quit [Remote host closed the connection]
bitdex has quit [Write error: Connection reset by peer]
sipa has quit [Remote host closed the connection]
zmnscpxj__ has quit [Remote host closed the connection]
jb55 has joined #bitcoin-wizards
morcos has joined #bitcoin-wizards
ghost43 has joined #bitcoin-wizards
justanotheruser has quit [Ping timeout: 260 seconds]
yanmaani has joined #bitcoin-wizards
sipa has joined #bitcoin-wizards
bitdex has joined #bitcoin-wizards
troygiorshev has joined #bitcoin-wizards
t-bast has quit [Remote host closed the connection]
t-bast has joined #bitcoin-wizards
shush has joined #bitcoin-wizards
justanotheruser has joined #bitcoin-wizards
rob01 has joined #bitcoin-wizards
shush has quit [Ping timeout: 260 seconds]
belcher has quit [Quit: Leaving]
shush has joined #bitcoin-wizards
proofofkeags has quit [Remote host closed the connection]
proofofkeags has joined #bitcoin-wizards
slivera has quit [Remote host closed the connection]
nick_freeman has quit [Remote host closed the connection]
nick_freeman has joined #bitcoin-wizards
laptop has joined #bitcoin-wizards
nick_freeman has quit [Ping timeout: 260 seconds]
nick_freeman has joined #bitcoin-wizards
AbramAdelmo has joined #bitcoin-wizards
laptop has quit [Remote host closed the connection]
AbramAdelmo has quit [Ping timeout: 260 seconds]
tromp has joined #bitcoin-wizards
mryandao has joined #bitcoin-wizards
davispuh has joined #bitcoin-wizards
nick_freeman has quit [Remote host closed the connection]
shush has quit [Remote host closed the connection]
shush has joined #bitcoin-wizards
setpill has quit [Quit: o/]
ghost43 has quit [Remote host closed the connection]
ghost43 has joined #bitcoin-wizards
dr-orlovsky has joined #bitcoin-wizards
troygiorshev has quit [Ping timeout: 256 seconds]
Guyver2 has joined #bitcoin-wizards
justanotheruser has quit [Quit: WeeChat 2.7.1]
justanotheruser has joined #bitcoin-wizards
rob01 has quit []
tromp has quit [Remote host closed the connection]
tromp has joined #bitcoin-wizards
ironmarx has joined #bitcoin-wizards
ironmarx has quit [Client Quit]
justanotheruser has quit [Ping timeout: 258 seconds]
kierank1 has joined #bitcoin-wizards
son0p has quit [Quit: leaving]
imawhale has quit [Ping timeout: 260 seconds]
nick_freeman has joined #bitcoin-wizards
nick_fre_ has joined #bitcoin-wizards
<sipa>
elichai2: if you want cool data structures... a list-like structure exists that allows accessing the i'th element in O(log n) time, and inserting/deleting anywhere in amortized O(log n) time
troygiorshev has joined #bitcoin-wizards
<sipa>
significantly higher memory usage (4 pointers per element) than a linked list, though
nick_freeman has quit [Ping timeout: 252 seconds]
<elichai2>
Worst case O(log N) accessing? Or average?
<sipa>
worst case O(log N) for accessing
<elichai2>
Because for average aren't all this just like a ordered binary tree?
<elichai2>
Oh
nick_fre_ has quit [Ping timeout: 252 seconds]
<elichai2>
Cool
<sipa>
actually, inserting/deleting are also worst case O(log n)
<sipa>
opposed to a linked list that has O(i) access time for accessing i'th position, and O(1) insert/delete
justanotheruser has joined #bitcoin-wizards
<sipa>
the idea is using a balanced tree (red-black tree or one of its variants), but keep track in every node how many (total) children that node has
<sipa>
so you can descend from the root, and if you want access the i'th element, if a node's left subtree has >=i elements, go left; if not, descend right and decrement i by k
<sipa>
where k is the number of elements in the left subtree
<sipa>
downside is that when inserting/deleting, you need to update all O(log n) parents' size
<elichai2>
Hmm
<elichai2>
Does this structure have a known name?
<sipa>
boost multiindex calls it a ranked index
roconnor has joined #bitcoin-wizards
<roconnor>
sipa: are you familiar with finger trees?
<sipa>
roconnor: i've heard the name
<elichai2>
I wonder if you can implement this struct on top of contiguous memory to also gain cache locality
<roconnor>
IIRC, it has the same properties except it also as O(1) queue and deque (from both the head and tail).
<elichai2>
Oh but then inserting can make it copy
<roconnor>
does so by keeping the head and tail of the tree very close to the root. and filling out the middle.
<roconnor>
finger trees also have log(n) append IIRC.
proofofkeags has quit [Remote host closed the connection]
<roconnor>
or concatentenation, depending on your venacular.
proofofkeags has joined #bitcoin-wizards
proofofkeags has quit [Remote host closed the connection]
proofofkeags has joined #bitcoin-wizards
troygiorshev has quit [Ping timeout: 260 seconds]
marcoagner has quit [Ping timeout: 260 seconds]
troygiorshev has joined #bitcoin-wizards
ghost43 has quit [Remote host closed the connection]
ghost43 has joined #bitcoin-wizards
<jonatack>
elichai2: fwiw, singly-linked lists are used frequently in common lisp (i assume in scheme, as well)... their main disadvantage (in CL) is that random access of list elements is O(n), but if you don't use lists for data for which arrays or hash tables would be a better fit, then lists/conses are a useful tool.
<sipa>
jonatack: if you need a persistent data structure, the balance shifts in their favor
<jonatack>
that are not only used for lists, alists, plists, sets, and trees, but for almost any ad hoc data structure
belcher has joined #bitcoin-wizards
<jonatack>
simple and versatile
<jonatack>
TIL about finger trees, thanks roconnor
<sipa>
is something like that used in std::deque in C++ STL implementations?
shush has quit [Remote host closed the connection]
shush has joined #bitcoin-wizards
TheoStorm has quit [Quit: Leaving]
<elichai2>
std::deque is really weird
<elichai2>
sipa: I know nothing about CLP but the "persistent data structure" starts falling apart in managed languages (because then everything can be persistent)
<sipa>
clp?
shush has quit [Ping timeout: 260 seconds]
imawhale has joined #bitcoin-wizards
<jonatack>
clp? (and sipa, can you expand on 'the balance shifts in their favor'?)
<elichai2>
Common lisp hehe, CL sorry
<jonatack>
oh ok. CL :)
<sipa>
jonatack: linked lists (and trees) are just very suitable for persistent data structures, so if you have a need for those, a linked list may be the right choice even when in a mutable setting you'd pick something else
<jonatack>
thanks
shush has joined #bitcoin-wizards
<roconnor>
PS the amorized cost guarentee falls apart somewhat which persistent structures if you go back to an older version. E.g. if a finger tree operation does lg(n) work once every lg(n) times it is called, then with a persistant structure, in principle you can rewind to that point and call the "O(1) amortized operation" over and over again in that state racking up ln(n) work each time.
AbramAdelmo has joined #bitcoin-wizards
son0p has joined #bitcoin-wizards
<jonatack>
sipa: was distracted by the gitian sig depends finally finishing the build. yes, agree
AbramAdelmo has quit [Ping timeout: 272 seconds]
surja795 has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
mryandao has quit [Ping timeout: 240 seconds]
kierank1 has quit []
<jonatack>
in CL I find them v useful in practice for empty lists and ones that have very few elements... in theory, perhaps like forward_lists in c++, but i have not used those yet
sipa has quit [Ping timeout: 240 seconds]
sipa has joined #bitcoin-wizards
Chris_Stewart_5 has quit [Ping timeout: 264 seconds]
nick_freeman has quit [Remote host closed the connection]
nick_freeman has joined #bitcoin-wizards
TheoStorm has joined #bitcoin-wizards
laptop has joined #bitcoin-wizards
surja795 has quit [Remote host closed the connection]
surja795 has joined #bitcoin-wizards
Chris_Stewart_5 has joined #bitcoin-wizards
slivera has joined #bitcoin-wizards
surja795 has quit [Ping timeout: 240 seconds]
jacob11 has joined #bitcoin-wizards
Guyver2 has quit [Quit: Going offline, see ya! (www.adiirc.com)]
son0p has quit [Quit: leaving]
Aranjedeath has joined #bitcoin-wizards
nick_freeman has quit [Remote host closed the connection]
surja795 has joined #bitcoin-wizards
AbramAdelmo has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
surja795 has quit [Ping timeout: 258 seconds]
AbramAdelmo has quit [Ping timeout: 260 seconds]
nick_freeman has quit [Ping timeout: 260 seconds]
nick_freeman has joined #bitcoin-wizards
nick_freeman has quit [Remote host closed the connection]
nick_freeman has joined #bitcoin-wizards
t-bast has quit [Remote host closed the connection]
t-bast has joined #bitcoin-wizards
t-bast has quit [Remote host closed the connection]
nick_freeman has quit [Remote host closed the connection]
t-bast has joined #bitcoin-wizards
nick_freeman has joined #bitcoin-wizards
t-bast has quit [Remote host closed the connection]
shush has quit []
t-bast has joined #bitcoin-wizards
t-bast has quit [Remote host closed the connection]
t-bast has joined #bitcoin-wizards
ghost43 has quit [Remote host closed the connection]
ghost43 has joined #bitcoin-wizards
surja795 has joined #bitcoin-wizards
AaronvanW has quit [Remote host closed the connection]
justanotheruser has quit [Ping timeout: 260 seconds]
jb55 has quit [Ping timeout: 240 seconds]
mryandao has joined #bitcoin-wizards
surja795 has quit [Ping timeout: 260 seconds]
Relis has quit [Quit: This computer has gone to sleep]
jb55 has joined #bitcoin-wizards
Relis has joined #bitcoin-wizards
justanotheruser has joined #bitcoin-wizards
laptop has quit [Ping timeout: 260 seconds]
surja795 has joined #bitcoin-wizards
AaronvanW has joined #bitcoin-wizards
fkinglag has quit [Ping timeout: 256 seconds]
troygiorshev has quit [Ping timeout: 264 seconds]
AaronvanW has quit [Ping timeout: 264 seconds]
unseddd has quit [Read error: Connection reset by peer]
unseddd has joined #bitcoin-wizards
surja795 has quit [Remote host closed the connection]