12

Let me start off by saying that this is not a homework question. I am trying to design a cache whose eviction policy depends on entries that occurred the most in the cache. In software terms, assume we have an array with different elements and we just want to find the element that occurred the most. For example: {1,2,2,5,7,3,2,3} should return 2. Since I am working with hardware, the naive O(n^2) solution would require a tremendous hardware overhead. The smarter solution of using a hash table works well for software because the hash table size can change but in hardware, I will have a fixed size hash table, probably not that big, so collisions will lead to wrong decisions. My question is, in software, can we solve the above problem in O(n) time complexity and O(1) space?

10
  • Do you have max limit to which elements can occur? Apr 24, 2014 at 6:17
  • @Aniket it is pretty big because it is part of the physical address, around 20 bits
    – Keeto
    Apr 24, 2014 at 6:18
  • Is there some limit on the maximum number of elements that can be in the array? Apr 24, 2014 at 6:25
  • @NikunjBanka Yes, the limit is the cache size. It is big but finite
    – Keeto
    Apr 24, 2014 at 6:27
  • Are you allowed to mutate the array - sorting it, for example? Also, since it's a cache, would an inexact heuristic be a viable option?
    – James_pic
    Apr 24, 2014 at 8:31

6 Answers 6

14

There can't be an O(n) time, O(1) space solution, at least not for the generic case.

As amit points out, by solving this, we find the solution to the element distinctness problem (determining whether all the elements of a list are distinct), which has been proven to take Θ(n log n) time when not using elements to index the computer's memory. If we were to use elements to index the computer's memory, given an unbounded range of values, this requires at least Θ(n) space. Given the reduction of this problem to that one, the bounds for that problem enforces identical bounds on this problem.

However, practically speaking, the range would mostly be bounded, if for no other reason than the type one typically uses to store each element in has a fixed size (e.g. a 32-bit integer). If this is the case, this would allow for an O(n) time, O(1) space solution, albeit possibly too slow and using too much space due to the large constant factors involved (as the time and space complexity would depend on the range of values).

2 options:

  • Counting sort

    Keeping an array of the number of occurrences of each element (the array index being the element), outputting the most frequent.

    If you have a bounded range of values, this approach would be O(1) space (and O(n) time). But technically so would the hash table approach, so the constant factors here is presumably too large for this to be acceptable.

    Related options are radix sort (has an in-place variant, similar to quicksort) and bucket sort.

  • Quicksort

    Repeatedly partitioning the data based on a selected pivot (through swapping) and recursing on the partitions.

    After sorting we can just iterate through the array, keeping track of the maximum number of consecutive elements.

    This would take O(n log n) time and O(1) space.

8
  • 3
    I don't believe an O(n) time, O(1) space you can drop the "I don't believe", there isn't. if there was solving distinctness problem could be done in O(n) time and O(1) space, by running the algorithm to get a candidate and then check its number of occurances. Your answer pretty much summarizes the possibilities, so +1.
    – amit
    Apr 24, 2014 at 10:05
  • @amit Thanks. I (hopefully accurately) incorporated this into my answer. Apr 24, 2014 at 11:17
  • 1
    I don't know a lower bound that says ED cannot be solved in that expected time and space using a randomized algorithm like a hash table. Reference?
    – Niklas B.
    Apr 24, 2014 at 13:47
  • @NiklasB. According to Wikipedia, the hash table solution falls under using elements to index the computer's memory, and thus aren't subject to these time and space bounds. But Wikipedia also mentions that the same lower bound was proven for randomized algorithms that don't fall under this, i.e. randomized algebraic decision tree model algorithms. Apr 24, 2014 at 14:00
  • I can't extract that at all from the Wikipedia article, but if you say so
    – Niklas B.
    Apr 24, 2014 at 14:17
3

As you say maximum element in your cache may e a very big number but following is one of the solution.

  1. Iterate over the array.
  2. Lets say maximum element that the array holds is m.
  3. For each index i get the element it holds let it be array[i]
  4. Now go to the index array[i] and add m to it.
  5. Do above for all the indexes in array.
  6. Finally iterate over the array and return index with maximum element.

TC -> O(N) SC -> O(1)

It may not be feasible for large m as in your case. But see if you can optimize or alter this algo.

3

A solution on top off my head :
As the numbers can be large , so i consider hashing , instead of storing them directly in array .

Let there are n numbers 0 to n-1 .
Suppose the number occcouring maximum times , occour K times .
Let us create n/k buckets , initially all empty.

hash(num) tells whether num is present in any of the bucket .
hash_2(num) stores number of times num is present in any of the bucket .

for(i = 0 to n-1)

  • if the number is already present in one of the buckets , increase the count of input[i] , something like Hash_2(input[i]) ++
  • else find an empty bucket , insert input[i] in 1st empty bucket . Hash(input[i]) = true
  • else , if all buckets full , decrease count of all numbers in buckets by 1 , don't add input[i] in any of buckets .
    If count of any number becomes zero [see hash_2(number)], Hash(number) = false .

This way , finally you will get atmost k elements , and the required number is one of them , so you need to traverse the input again O(N) to finally find the actual number .

The space used is O(K) and time complexity is O(N) , considering implementaion of hash O(1).
So , the performance really depends on K . If k << n , this method perform poorly .

2

I don't think this answers the question as stated in the title, but actually you can implement a cache with the Least-Frequently-Used eviction policy having constant average time for put, get and remove operations. If you maintain your data structure properly, there's no need to scan all items in order to find the item to evict.

The idea is having a hash table which maps keys to value records. A value record contains the value itself plus a reference to a "counter node". A counter node is a part of a doubly linked list, and consists of:

  • An access counter
  • The set of keys having this access count (as a hash set)
  • next pointer
  • prev pointer

The list is maintained such that it's always sorted by the access counter (where the head is min), and the counter values are unique. A node with access counter C contains all keys having this access count. Note that this doesn't increment the overall space complexity of the data structure.

A get(K) operation involves promoting K by migrating it to another counter record (either a new one or the next one in the list).

An eviction operation triggered by a put operation roughly consists of checking the head of the list, removing an arbitrary key from its key set, and then removing it from the hash table.

2

It is possible if we make reasonable (to me, anyway) assumptions about your data set.

As you say you could do it if you could hash, because you can simply count-by-hash. The problem is that you may get non-unique hashes. You mention 20bit numbers, so presumably 2^20 possible values and a desire for a small and fixed amount of working memory for the actual hash counts. This, one presumes, will therefore lead to hash collisions and thus a breakdown of the hashing algorithm. But you can fix this by doing more than one pass with complementary hashing algorithms.

Because these are memory addresses, it's likely not all of the bits are actually going to be capable of being set. For example if you only ever allocate word (4 byte) chunks you can ignore the two least significant bits. I suspect, but don't know, that you're actually only dealing with larger allocation boundaries so it may be even better than this.

Assuming word aligned; that means we have 18 bits to hash.

Next, you presumably have a maximum cache size which is presumably pretty small. I'm going to assume that you're allocating a maximum of <=256 items because then we can use a single byte for the count.

Okay, so to make our hashes we break up the number in the cache into two nine bit numbers, in order of significance highest to lowest and discard the last two bits as discussed above. Take the first of these chunks and use it as a hash to give a first part count. Then we take the second of these chunks and use it as a hash but this time we only count if the first part hash matches the one we identified as having the highest hash. The one left with the highest hash is now uniquely identified as having the highest count.

This runs in O(n) time and requires a 512 byte hash table for counting. If that's too large a table you could divide into three chunks and use a 64 byte table.

Added later

I've been thinking about this and I've realised it has a failure condition: if the first pass counts two groups as having the same number of elements, it cannot effectively distinguish between them. Oh well

1

Assumption: all the element is integer,for other data type we can also achieve this if we using hashCode()

We can achieve a time complexity O(nlogn) and space is O(1).

First, sort the array , time complexity is O(nlog n) (we should use in - place sorting algorithm like quick sort in order to maintain the space complexity)

Using four integer variable, current which indicates the value we are referring to,count , which indicate the number of occurrences of current, result which indicates the finale result and resultCount, which indicate the number of occurrences of result

Iterating from start to end of the array data

  int result = 0;
  int resultCount = -1;
  int current = data[0];
  int count = 1;

  for(int i = 1; i < data.length; i++){
       if(data[i] == current){
            count++;
      }else{
           if(count > resultCount){
               result = current;
               resultCount = count;
           }
           current = data[i];
           count = 1;
       }
  }
  if(count > resultCount){
      result = current;
      resultCount = count;
  }
  return result;

So, in the end, there is only 4 variables is used.

6
  • log(1) + log(2) + ... + log(n) = log(1*2*....*n) = log(n!) which is in Theta(nlogn). I don't understand where your claim for almost O(n) comes from.
    – amit
    Apr 24, 2014 at 9:53
  • 2
    In addition, inserting an element to an arbitrary location in an array is O(n), because you need to "push" all elements to its right one step further. If you want to use a tree/skip list to obtain O(logn), you are going to suffer from much higher constants.
    – amit
    Apr 24, 2014 at 9:55
  • (I downvoted before the answer was fixed, and revoked my downvote when it was)
    – amit
    Apr 24, 2014 at 11:13
  • @PhamTrung: sorry, I did this by mistake. I didn't see the fix. Please do a dummy edit in your answer so I can cancel my downvote. Apr 24, 2014 at 11:28
  • @EyalSchneider It's ok :)
    – Pham Trung
    Apr 24, 2014 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.