On 11/30/15 4:58 PM, Steven Schveighoffer wrote:
> On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:
>> On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
>>> What about when element i is matched, swap it with the (i/2)'th element?
>>
>> Randomization is essential - without it you have thrashing if you search
>> for 2 elements in alternation. -- Andrei
>>
>
> What about selecting a random element in 0..k/2 instead of 0..k-1?

I think complexity would stay the same. Choosing a tighter range puts a greater weight on the last search than on recent searches.

One thing I like is that I choose 0..k, not 0..k-1, which means it's possible that the element stays put (no change in position). That reduces thrashing for the top (most frequently searched) few elements.


andrei

On Monday, 30 November 2015 at 21:50:09 UTC, Andrei Alexandrescu wrote:
> On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
>> What about when element i is matched, swap it with the (i/2)'th element?
>
> Randomization is essential - without it you have thrashing if you search for 2 elements in alternation. -- Andrei

You'd end up swaping the 2 element in front, but keep them both in front, so that sounds like it would have the same behavior as the randomized algorithm.

Where it gets hairy, is when you access 2 elements in the array that would swap each other without getting in the front (because they are at 2n and 2n + 1 with n big).

On Mon, 30 Nov 2015 16:58:16 -0500, Steven Schveighoffer wrote:

> On 11/30/15 4:50 PM, Andrei Alexandrescu wrote:
>> On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
>>> What about when element i is matched, swap it with the (i/2)'th
>>> element?
>>
>> Randomization is essential - without it you have thrashing if you search for 2 elements in alternation. -- Andrei
>>
>>
> What about selecting a random element in 0..k/2 instead of 0..k-1?
> 
> -Steve

You can use that to put a hard upper bound of O(log n), and maybe you'll want to use that. However, that also means you have greater odds of a single rare query making it to the front of the stack.

If you want to prevent that and still get a guarantee of O(log n), you could choose a range of floor(sqrt(k))..k/2.

On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu wrote:
> With RStF, worst case search time remains O(n), as is the unsuccessful search. However, frequently searched elements

If you just do a linear search then shifting down the array in another pass won't change the complexity. O(2N) == O(N) But you could also just shift down the array while searching since if the elements are less than the cacheline-size then you already have everything in registers/first level cache.

(The write back cost from cache to memory is contextual and depends on many factors.)

On Monday, 30 November 2015 at 22:11:09 UTC, deadalnix wrote:
> On Monday, 30 November 2015 at 21:50:09 UTC, Andrei Alexandrescu wrote:
>> On 11/30/15 4:41 PM, H. S. Teoh via Digitalmars-d wrote:
>>> What about when element i is matched, swap it with the (i/2)'th element?
>>
>> Randomization is essential - without it you have thrashing if you search for 2 elements in alternation. -- Andrei
>
> You'd end up swaping the 2 element in front, but keep them both in front, so that sounds like it would have the same behavior as the randomized algorithm.
>
> Where it gets hairy, is when you access 2 elements in the array that would swap each other without getting in the front (because they are at 2n and 2n + 1 with n big).

Imagine that there are 1000 elements, 500th elements is X and 1000th element is Y.

1) search for Y: Y is last, takes 1000 iterations, swaps X<->Y
2) search for X: X is last, takes 1000 iterations, swaps X<->Y
3) back to 1

On 11/30/2015 03:15 PM, Denis Koroskin wrote:

Forget the algorithms! Denis is back... :)

Ali

On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu wrote:
> So let's improve on that: whenever an element is found in position k, pick a random number i in the range 0, 1, 2, ..., k inclusive. Then swap the array elements at indexes i and k. This is the Randomized Slide to Front strategy.
>
> With RStF, worst case search time remains O(n), as is the unsuccessful search. However, frequently searched elements migrate quickly to the front - it only takes O(log n) searches to bring a given value at the front of the array.

Something is wrong with the math here.  The randomization means that you must assume that you get element k-1 in the worst case, so if you repeatedly search for the same element you need O(N) repeats to move it to the front, so you get O(N^2) complexity for moving any element to the front.

Right?

You are probably thinking about the average case analysis, which is a more sensible theoretical concept for randomized algorithms than worst case, but then you need a model for what is typical.

On Mon, 30 Nov 2015 23:27:24 +0000, Ola Fosheim Grøstad wrote:

> On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu wrote:
>> So let's improve on that: whenever an element is found in position k, pick a random number i in the range 0, 1, 2, ..., k inclusive. Then swap the array elements at indexes i and k. This is the Randomized Slide to Front strategy.
>>
>> With RStF, worst case search time remains O(n), as is the unsuccessful search. However, frequently searched elements migrate quickly to the front - it only takes O(log n) searches to bring a given value at the front of the array.
> 
> Something is wrong with the math here.  The randomization means that you must assume that you get element k-1 in the worst case, so if you repeatedly search for the same element you need O(N) repeats to move it to the front, so you get O(N^2) complexity for moving any element to the front.
> 
> Right?
> 
> You are probably thinking about the average case analysis, which is a more sensible theoretical concept for randomized algorithms than worst case, but then you need a model for what is typical.

People typically use lax terminology. Here, when someone doesn't specify whether they're talking about average or worst case complexity for an algorithm, they're probably talking about average case. Similarly for amortized algorithms. Andrei is no doubt aware of the worst case (which in this case is O(inf), not O(N)) and has responded to people talking about ways to reduce the worst case.

This doesn't mean Andrei was wrong or misspoke; it means that he could have been marginally clearer. Most people instantly grok the intent, but some who are blessed with pedantry don't.

Identifying these cases is a skill that took me years to learn.

On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu wrote:
[...]
> One well-known search strategy is "Bring to front" (described by Knuth in TAoCP). A BtF-organized linear data structure is searched with the classic linear algorithm. The difference is what happens after the search: whenever the search is successful, the found element is brought to the front of the structure. If we're looking most often for a handful of elements, in time these will be near the front of the searched structure.
[...]
> Another idea is to just swap the found element with the one just before it. The logic is, each successful find will shift the element closer to the front, in a bubble sort manner. In time, the frequently searched elements will slowly creep toward the front. The resulting performance is not appealing - you need O(n) searches to bring a given element to the front, for a total of O(n * n) steps spent in the n searches. Meh.
>
> So let's improve on that: whenever an element is found in position k, pick a random number i in the range 0, 1, 2, ..., k inclusive. Then swap the array elements at indexes i and k. This is the Randomized Slide to Front strategy.
>
[...]
> Insertion and removal are both a sweet O(1), owing to the light structuring: to insert just append the element (and perhaps swap it in a random position of the array to prime searching for it). Removal by position simply swaps the last element into the position to be removed and then reduces the size of the array.
[...]
> Andrei

It seems to me you're trying to implement the array based equivalent of Splay Trees (Splay Array rhymes, btw). Would that be a close enough description?

I'm assuming you're trying to optimize for some distribution where a minority of the elements account for the majority of queries (say, Zipfian).

Here are some ideas that come to mind. I haven't thought through them too much so everyone's welcome to destroy me.

Rather than making index 0 always the front, use some rotating technique similar to what ring buffers do.

Say we initially have elements ABCDE (front at 0) and we search for C. We swap the left of front (cycling back to the end of the array, thus index 4) with the new front. We now have the following array at hand: ABEDC, front at 4 (logically CABED).

Obviously we shouldn't change front if the queried element is already it.

An immediate problem with this technique is that we'll frequently pollute the front of the array with infrequent items. Say these are the number of queries made so far for each element: A:7, B:5, C:2, all others 0. Also, assume that this is the state of the array at this point: DEABC, front at 2. Say we now query for B. This is the new state: DBAEC, front at 1 (logically BAECD). Having E in front of C is undesirable, so we need a way to avoid that.

From now on I'll refer to indexes as the logical index. That is, let i be (front + index) % size. For the sake of brevity, let d be the distance between the element and the front = i - front. Let q be the number of successful queries performed so far.

What I have in mind boils down to decide between:
- move a newly queried element at logical position i to the left of front (technique above). Let's call it move-pre-front for the lack of a better name;
- bubble the element up to some position between [0, i), not necessarily max(0, i - 1).

Augmenting the array with the number of queries for each element would tremendously help the decision making, but I'm assuming that's undesirable for a few reasons like:
- the array can't be transparently used in algorithms unaware of the structure;
- alignment;
- data bloating.

My immediate thought is to use some heuristic. For instance, say we have some threshold k. If d <= k, we bubble up s <= d positions to the left, where s could be computed using some deterministic formula taking d, q and/or k into account, or just randomly (Andrei's RStF). If d > k, we move-pre-front the element.

The threshold k could be computed as a factor of q. Say, sqrt(q), log q or log^2 q (logarithm base 2).

Thoughts?

Marcelo

On Tuesday, 1 December 2015 at 01:12:39 UTC, Chris Wright wrote:
> People typically use lax terminology. Here, when someone doesn't specify whether they're talking about average or worst case complexity for an algorithm, they're probably talking about average case.

Don't use lax terminology when doing complexity analysis. Average case analysis is much much much harder to do than worst case/amortized.