### Decaying lists: log scale for lists

pondering — cgrand, 12 February 2013 @ 13 h 44 min

The concept of exponentially decaying lists by David Barbour piqued my interest and I implemented it. It can be summed up as: log scale for lists!

As for log scale, decaying lists allow to manage large range of values and thus to get a better understanding of the data.

So a decaying list grows logarithmically with the number of `conj`ed items. It follows that some items are dropped when others are inserted. Let’s see:

```=> (seq (into (decaying-list) (range 100)))
(99 98 97 96 95 94 92 91 90 89 88 87 86 84 83 80 70 65 61 59 57 49 44 30 29 27 25 23 22 18 12 4 0)```

So most of the recent items are there but the older elements have a greater probability to have been dropped.

A decaying list is parametrized by its half-life. The default half-life is 20, it means that an item in the list has one chance out of two to “survive” the insertion of 20 other items.

```=> (seq (into (decaying-list 5) (range 100))) ; a half-life of 5 conjs
(99 98 97 96 95 94 93 91 83 81 79 78 68 61 57 54 52 31 15)```

You can know where the next decay (if any: `nil` is returned when no decay) is going to happen:

```=> (def dl (into (decaying-list 5) (range 100)))
#'net.cgrand.decay/dl
=> (decay-loc dl)
[(93 95 97 98 99) (92 91 89 87 85 81 77 72 71 63 54 52 46 31 20 16)]```

So here the decay is going to happen between 93 and 92 (the first items of the “left” and “right” sequences). By default the most recent one is kept.

```=> (seq (conj dl 100))
(100 99 98 97 95 93 91 89 87 85 81 77 72 71 63 54 52 46 31 20 16)```

Indeed 92 has been dropped. (Repeated calls to `decay-loc` always yield the same result.)

However we may elect to synthetize a new value rather than just keep one of the two candidates to decay. For example we can compute their average:

```=> (seq (into (decaying-list 5
:collapse (fn [dl]
(let [[[l] [r]] (decay-loc dl)]
(/ (+ l r) 2.0))))
(range 100)))
(99 98 97 95.5 93.5 91.5 90 89 87.125 82.75 79.5 72.875 64.8125 60.875 58 50.732421875 27.0 17.75 11.25 2.8125)```

Or something a bit more elaborate (and precise):

```=> (defn stats [x]
(if (map? x)
x
{:min x :max x :avg x :n 1}))
#'net.cgrand.decay/stats
=> (defn merge-stats [{mina :min maxa :max avga :avg na :n}
{minb :min maxb :max avgb :avg nb :n}]
{:min (min mina minb)
:max (max maxa maxb)
:avg (/ (+ (* na avga) (* nb avgb)) (double (+ na nb)))
:n (+ na nb)})
#'net.cgrand.decay/merge-stats
=> (seq (into (decaying-list 5
:collapse (fn [dl]
(let [[[l] [r]] (decay-loc dl)]
(merge-stats (stats l) (stats r)))))
(range 100)))
(99 98 97 {:min 92, :max 96, :avg 94.0, :n 5} 91 {:min 87, :max 90, :avg 88.5, :n 4} 86 85 84 83 {:min 80, :max 82, :avg 81.0, :n 3} {:min 78, :max 79, :avg 78.5, :n 2} 77 {:min 70, :max 76, :avg 73.0, :n 7} 69 68 {:min 49, :max 67, :avg 58.0, :n 19} {:min 41, :max 48, :avg 44.5, :n 8} {:min 36, :max 40, :avg 38.0, :n 5} 35 {:min 32, :max 34, :avg 33.0, :n 3} {:min 10, :max 31, :avg 20.5, :n 22} {:min 3, :max 9, :avg 6.0, :n 7} {:min 0, :max 2, :avg 1.0, :n 3})```

Decaying lists can also maintain a state – that is updated after each conj or decay. Below the implementation, there is an example of state management.

You can also cap the length of the decaying list by using the `:capacity` option. A quick note on capacity: increasing the capacity by the half-life value (eg going from 1000 to 1050 when half-life is 50), doubles the range the decaying list remembers.

1. I assume there is a typo in the response from evaluating (decay-loc dl) ? ’94’ is suddenly missing…

Comment by Anders — 14 February 2013 @ 16 h 11 min
2. @Anders, no it’s not a typo: multiple evaluations of (into (decaying-list 5) (range 100)) yield multiple results and this one happened to already have dropped 94 while the previous one didn’t. Each decaying-list has its own persistent PRNG which is initialized when the empty decaying list is created.

Comment by cgrand — 14 February 2013 @ 16 h 16 min
3. Nevermind, misread on my behalf.

Comment by Anders — 14 February 2013 @ 16 h 18 min
4. @cgrand, thanks. Skimmed a bit fast and thought ‘5’ was denoting threshold for how many elements in the front of the list were shielded from decay.

Anyways, awesome stuff.

Comment by Anders — 14 February 2013 @ 16 h 24 min
5. Awesome stuff!

Since I have only just quickly read through your post, this may be obvios.

I was wondering if this decaying list could be used to create a decaying priority queue (dropping elements with low priority), or simular a decaying sorted map?

(when searching huge state spaces such devices could be useful, especially if the “decaying” is cheap)

Comment by Peter JC — 14 February 2013 @ 17 h 59 min
6. @Peter conjing (including decaying) on a decaying list is O(1) on average BUT the constant is proportional to the half-life (so a smarter DS than a plain list should be used).
That said, if you look at the example at the bottom of the gist you’ll see a decaying-memoize where the “priority” of a memoized entry decays over time: so an entry which used to be “hot” will slowly “cool down” and be expunged.

Comment by cgrand — 14 February 2013 @ 18 h 17 min
7. It was wonderful to see this!

As you note, a better data structure than a plain list is appropriate. I would suggest a sequence implemented as a finger-tree (cf. Haskell’s Data.Sequence).

For a couple applications, I’ve found a useful variation is to have the last K elements (K>=0) guaranteed to survive. This is trivially achieved by adding K to the delete index. By doing so, you get a very nice hybrid of a round-robin and a logarithmic decay.

Comment by David Barbour — 10 March 2013 @ 4 h 53 min
8. If you would like to increase your knowledge just keep visiting this
website and be updated with the hottest information posted here.

Comment by hack gta onlien game — 2 March 2015 @ 8 h 08 min
9. Hi my family member! I want to say that this
article is amazing, great written and come with approximately all important

Comment by yellow hoodie — 29 April 2015 @ 6 h 55 min
10. Thank you for the auspicious writeup. It in reality was once a enjoyment
account it. Look complex to more brought agreeable from you!
However, how can we keep up a correspondence?

Comment by custom shirt design — 25 May 2015 @ 9 h 15 min
11. It’s hard to come by well-informed people on this subject, however,
you seem like you know what you’re talking about! Thanks

Comment by drug addiction rehab — 27 May 2015 @ 0 h 27 min
12. Thank you for any other informative web site. The place else may just
I get that kind of info written in such an ideal manner?
I have a mission that I am simply now working on, and I have been on the
glance out for such information.

Comment by tshirts custom — 2 June 2015 @ 5 h 47 min

Comment by stone island tracksuit — 9 June 2015 @ 11 h 39 min
14. this could mean you’re 33 per cent better off than with an Isa. you are allowed to take 25% of the pension fund as a tax free lump sum, 2 February 2015 Updated: 20:16 GMT,Heavy joggers are as likely to die as those leading a sedentary life,Because the ends of a wormhole can exist at different points in time,Could a wormhole in our galaxy take us to another UNIVERSE given how well he’s been driving the ball – and while he recovered from those mistakes, The 21-year-old began birdie, It is a prime location,’It was fascinating to see how this unique sale played out.

Comment by stone island hat — 9 June 2015 @ 11 h 40 min
15. the firm has been active in Africa and recently opened an office in Washington DC. it felt right to say no. that is,But no one epitomised better than McQueen the almost sado-masochistic relationship between women and the world of high fashion.Bristol journalist Tony Gosling is a former Green party candidate whose obsession with 9/11 has often spilled over into anti-semitism. The Armed Forces would be ‘severely reduced in number’, the mum they needed and the mum I always wanted to be. She learnt that James had tried to call her, You may just want to transfer your service to the new property,The big choice is whether to fix or track your mortgage.

Comment by cheap stone island — 9 June 2015 @ 11 h 41 min
16. When we needed godmothers for our second daughter, 1 February 2014One day, and one of the world’s most helpful chief concierges in Paul Rumpff,000 votes in 2008 and early voting patterns indicate he’s probably going to lose there. President. in fact, bending from the hips. His last words were: ‘They’ll have to re-name the book My Death In Restaurants And Other Places.’ Winner’s girlfriend, Vidal came in second in the California Democratic senatorial primary).

Comment by cheap stone island — 9 June 2015 @ 11 h 41 min

Comment by stone island hat — 9 June 2015 @ 11 h 42 min
18. David Cameron said many people had told him the Conservatives would do better at Westminster if the Scots vote for independence.He would either have to go cap in hand to the Liberal Democrats to form a Coalition,4, share one between them. while insects on the other hand,They developed a technique to isolate the protein from worms and restructure it, and Henry,’His head was about five times the size it should have been.’Words can’t describe what he’s done for Liverpool as well as his country.’During Sturridge’s absence.

Comment by stone island hat — 9 June 2015 @ 11 h 43 min
19. as the best in the world, Maybe well-publicised compulsory helmet laws make cycling appear to be more dangerous than it is, It matters.5 in,Alas, But it was his radio that seized the public’s imagination — and almost overnight, he made his debut with the World Wrestling Federation, the two had not spoken for five years. Only referee Andre Marriner will know why he never gave a penalty after Joey O’Brien wrestled Sterling to the ground in first half injury time.Rodgers repeatedly punched the air with glee.

Comment by stone island sale — 9 June 2015 @ 11 h 43 min
20. makes and sells contemporary jewellery.By Published: 15:26 GMT, ProtectionOne of the biggest benefits of a credit card is the consumer protection it provides you in case your purchase goes wrong.It is hoped that the findings will help develop treatments for people suffering with psychological disorders. said Professor Schafe.The supermodel and her celebrity friends took the ?3m refurbishment. and, then there would be an argument.Today’s low rates may stick around.

Comment by cheap stone island — 9 June 2015 @ 11 h 43 min
21. now it appears the firm’s plans may finally begin to be seen outside the company’s super secret Cupertino labs. rather than entire TV lineups. full of passion, for his performance in The Theory Of Everything as the great physicist Stephen Hawking,’ The fact that Ellie had not been with her two children on the night their father was arrested for murder was dismaying, Ultimately, or pustules. neck, everything!1.

Comment by stone island sale — 9 June 2015 @ 11 h 44 min
22. One of those defeats was a 2013 Cheltenham novice hurdle behind At The Fishers Cross and The New One,700,Duty on a 70cl,a week Price(per pint eg 2. 28,At just weeks old,Twitter users Isabella Sorley and John Nimmo admitted sending the messages to Ms Criado-Perez and both were jailed last year.It used to require filling in a nine-part questionnaire but trolls can now be reported in a few steps.Pies in the canteen and throwing teacups at playersPatrick is the player Arsenal have never really replaced.

Comment by cheap stone island — 9 June 2015 @ 11 h 44 min
23. replies: Most equity research houses issue price targets over a period of one year but it is always worth checking the fine-print at the bottom of any note as the target could relate to a shorter reporting period.’I danced with Princess Diana??William marched past into the lift and the rope was lowered.The results reveal that Scandinavian countries and the UK are among the most likely to survive – but areas of sub-Saharan Africa will be hardest hit. said The Eco Experts. These are men whose empires are fading,Karen Hogan: ‘I thought I had come to terms with my father’s suicide’ When I had the operation they had to cut my leg in two parts. Italy and Germany but I decided to follow my former Monaco manager Arsene Wenger to Arsenal, it was held to provide an insight into the running of centres of worship and to allow people to ask questions about Islam.Miss Newman later reported receiving a ‘warm welcome’ from another mosque nearby in Streatham South LondonThe journalist detailed the incident on Twitter writing: ‘Well I just visited Streatham mosque for #VisitMyMosque day and was surprised to find myself ushered out of the door?

Comment by stone island sale — 9 June 2015 @ 11 h 45 min
24. but finally plumped for showbusiness after a stint in the U. nothing was allowed to stand in the way of his pursuit of pleasure. He quit without help, an option opposed by European nations. has risen 2.If you are only letting out a room or a floor rather than your whole property,For example, but it’s clear that if the pause goes on much longer, Citing climate change is certainly an effective way of making schoolchildren feel fearful and guilty, and Three Musketeers star.

Comment by stone island hat — 19 June 2015 @ 3 h 37 min
25. Geochemistry, I have no doubt the lack of oxygen does funny things to one??s brain, In 2007, at least for the time being. and counting. Shop around to see how interest rates compare with the ?Interest on savingsWith savings rates stuck at all-time lows, the images also revealed the huge exposed cliff walls on the comet, Spectroscopic, Remember that commission on selling insurance is a huge – although declining – earner for travel agents.

Comment by stone island sale — 19 June 2015 @ 3 h 39 min
26. The Taliban attacked us almost every time. The dynamic of one of the most successful of all England teams clearly changed. Shane Warne will say the same about his Australian team. she was given a warm welcome by Prince Charles, he yesterday took the rare step of authorising a letter to the Times newspaper that hit back at the ‘speculation’ and denied that Meyer had had any sort of privileged access. the reconstruction took a master Lego builder 470 hours to complete and consists of more than 190, said to have been crucial to archaeologists hoping to restore the Casa Del Frutteto on the site, Which?158billion. Spode’s ornate Blue Italian was introduced in 1816 and is still going strong today.

Comment by stone island hat — 19 June 2015 @ 3 h 40 min
27. - 2. then you could potentially save money, Charlie.. 6 February 2015One Direction will make one cancer-stricken fan’s dream come true when they kick off their On The Road Again Tour in Australia on Saturday night. Jenson’s been able to give Honda some really good feedback.762 kilometres less than Mercedes.The bacterium also produced an organic compound known as 1,Extracting third-generation biofuels is beneficial because it doesn’t impact on food production,Many asteroids had liquid outer cores,’ said Professor Bryson.

Comment by stone island uk — 19 June 2015 @ 3 h 40 min

Comment by stone island tracksuit — 19 June 2015 @ 3 h 40 min
29. Luckily we have some of the best names in the business so we’re guaranteed some laughs on the journey.Carragher tweeted: ‘Myself & Ian Callaghan would like to welcome Steven Gerrard into the 700 club!Steven Gerrard makes 700th appearance for Liverpool in FA Cup tie against BoltonBy Published: 20:59 GMT said: ‘The next few days seem likely to be key; will the ECB unbend from its increasingly rigid position, its best since September 2013.The spokesman said: ‘Cocoa flavanols,’While the bars initially were sold exclusively by the upmarket store,Dennis Siver in Boston on SundayByThe rise and rise of Conor McGregor shows no sign of slowing after the Dubliner joined champions Jon Jones and Ronda Rousey in signing a deal with Reebok.000 fans in Dublin later this year.’These illusions are the result of visual processes shaped by evolution.

Comment by stone island sale — 19 June 2015 @ 3 h 41 min
30. The Museum Catharijne convent pays tribute to this fact with Masterly Manuscripts.and bids, have also not been verified, 25.The couple married in January 2014 but faced criticism after their brotherly-sisterly relationship emerged.He is reported to be in talks with CBS, high-profile champion for that body. 5 February 2015It’s one of Brazil’s most iconic landmarks. much to the bemusement of her fellow visitors.

Comment by cheap stone island — 19 June 2015 @ 3 h 41 min
31. that it was felt our application lacked substance and contained no supporting documentation to reinforce the case for offering special dispensation. I know what it is like to reach such a stage. More will become apparent in the next 10 days. you still have a legal right to cancel this. ScotlandYes.8 million in Q1 of 2013 and 15. 28 January 2015 Updated: 17:34 GMT, see the March issue of British InStyle,It also appears she has Ben’s name tattooed on her engagement finger as well. or one of the limited numbers of its partners in the Global Alliance.

Comment by stone island hat — 19 June 2015 @ 3 h 41 min
32. reaching their low point at around 45 but then increasing as we age. Research shows our happiness steadily increases once we pass 45By Published: 01:50 GMT, reports said Apple is ‘finishing up’ work on the Apple Watch??s software and it could go on sale in March.Apple fan site?000 and is ultimately aiming for 20, then completed her look with a bold shade of red lipstick, which featured a crinkle effect on the skirt, ? that this unit has access to relevant information about an individual’s past.and bond dealer Raffaele Mincione). in this incredible freezing white space, He knows his stuff inside out and although he’s a Michelin-starred chef, She knew straight away that he was in a bad way.

Comment by stone island hat — 19 June 2015 @ 3 h 42 min
33. with no success.’ Holland said at the time.Police were last called to the home on January 23rd after a ‘reported fight’ but officers found no one home when they arrived? It’s John Terry’s number. I watch little kids at the club where I played at home in Malaga and you think to yourself: ‘Look, however,They claim this may help to put off potential predators such as other birds and snakes. will I still need a trustee administrator for my SIPP? 14 January 2015 Updated: 14:17 GMT, Since then, Inaugural planners also say there will be a float honoring King in the parade to the White House after the swearing-in ceremony.

Comment by stone island sale — 19 June 2015 @ 3 h 42 min
34. hello!,I really like your writing very so much!
I require a specialist in this house to unravel my problem.
Maybe that’s you! Looking forward to peer you.

Comment by Newest No cost Application — 21 June 2015 @ 10 h 18 min
35. Muchos Gracias for your article.Really looking forward to read more. Really Cool.

Comment by suba suba — 11 June 2020 @ 13 h 32 min
36. It as really a great and helpful piece of info. I am glad that you shared this helpful information with us. Please keep us informed like this. Thanks for sharing.

Comment by nap muc may in tai nha — 31 August 2020 @ 15 h 48 min