4

I have an audio input stream which takes in the current volume level of playing music. Then over a certain windows size (which can range from 5 to 40), of the latest volumes, I want to keep track of the highest and lowest values inside the window. so on each iteration the oldest value that was added is removed and the newest volume level reading is added.

so say if i ran the program for 8 iterations with a window of 5 and this would result. with only the low and high values being of importance.

add 2

2

add 4

2 4

add 3

2 3 4

add 2

2 2 3 4

add 7

2 2 3 4 7

-first 2 removed from list add 9

2 3 4 7 9

4 removed , add 5

2 3 5 7 9

3 removed , add 2

2 2 5 7 9

etc

what would be the most efficient way to do this and using what type of collections?

edit note that this loop is being run constantly on a separate thread

values are floats

Code Enthusiastic
  • 2,827
  • 5
  • 25
  • 39
Thomas
  • 435
  • 6
  • 20
  • 1
    here you have 2 pair of operations. min\max and add\remove. Which one occur more often?? – UmNyobe Sep 29 '13 at 09:07
  • on each iteration a number is added and removed and then the min and max found, they occur the same amount – Thomas Sep 29 '13 at 09:11

3 Answers3

3

on each iteration a number is added and removed and then the min and max found, they occur the same amount

Use a balanced binary tree such as Treemap, so all operation will be O(log n) in worst case. I believe that if these operations happen succesively, there is no point having 3 operations being O(1) and one being O(n).

Btw n=5 is so small I dont see why you should be concerned too much about inefficiency.

Edit: To keep track of the order of the objects you can use a simple queue as a secondary structure. When you need to delete you remove the head of the queue and you use it as key to remove in your tree.... adding and removing take constant time.

note: can stop here, original idea below

A better complexity data structure will be a tweaked min-max heap, it provides a nice trade-off between all your operations :

  • Insertion is O(log n)
  • deletion is O(n)
  • Min and Max are both O(l).

if you were deleting only the max/min, deletion would be logarithmic. The tweak is to implement a general purpose delete which is log n

Community
  • 1
  • 1
UmNyobe
  • 22,539
  • 9
  • 61
  • 90
  • Thanks. Its for an android app which calculates if the volume at every instance possible is above a % of the sum of the the high and low values inside the window. My knowledge of speeds is pretty limited so I just wanted to make it as fast as possible. – Thomas Sep 30 '13 at 01:02
  • 1
    I'm a little confused with the deletion, how would you keep track of the order in which values were added, in regards to your idea? – Thomas Sep 30 '13 at 01:17
  • yes in your problem you shoot down the oldest. I forgot. edited – UmNyobe Sep 30 '13 at 07:40
  • did you mean TreeSet instead of TreeMap because TreeMap sorts by keys? – Thomas Oct 01 '13 at 05:31
1

You can use a linked list since you want to store duplicate values in your list. Also since you plan to add to the last element you use the addLast() method of LinkedList API. In your own add() method keep a check for the size. If the size reaches the maximum size you can call the removeFirst() method of the link list and then the addLast() method. This way your link list size will remain constant at 5

public class Tester {
private LinkedList<Integer> values = new LinkedList<Integer>();
private static final int MAX_VAL = 5;

public void addvalue(int val) {
    if (values.size() == this.MAX_VAL) {
        values.removeFirst();
    }
    values.addLast(val);
}

public int getMaxValue(){           
    return Collections.min(values);
}

public int getMinValue(){
    return Collections.max(values);
}

}

Pratik Shelar
  • 3,154
  • 7
  • 31
  • 51
  • 1
    thanks, how would i keep track of the min and max values of the list efficiently? – Thomas Sep 29 '13 at 08:44
  • Since you are using integers you can directly call Collections.sort on your linked list – Pratik Shelar Sep 29 '13 at 08:50
  • if i sort it though and then removeFirst it will remove the lowest value and not the earliest value that was added? – Thomas Sep 29 '13 at 08:55
  • I had forgotten about the api methods of max and min. I have edited my code. Do have a look. – Pratik Shelar Sep 29 '13 at 09:09
  • This is Theta(totalNumberOfElements * WINDOW_SIZE). Why maintain a separate collection. Why not iterate backwards from the end(tail), while maintaining min and max ? The complexity would be the same. – bsd Sep 29 '13 at 14:21
0

Since the values are integers 5 to 40, if the window was large we could try for a good average case time by storing array count[] which keeps a tally of the number of windows at each volume. Then adding the new element and deleting the last (keeping a Queue such as LinkedList) is constant time, unless the count at low or high drops to 0. Then search values one by one starting at the last best, which is O(35) but could be even cheaper in practice especially with a large window.

In a way this is a constant time solution, in the actual input, the number of volume elements you add. It's O(nk) where it sounds like k is only thirty-some volumes. I suspect we could prove the average case time is \Theta(nk/w) where w is the window size, assuming reasonably distributed data.

It really doesn't sound like a high throughput operation (how often can the user change the volume, all of hundreds of times??) but that's how I'd implement it under those conditions.

clwhisk
  • 1,805
  • 1
  • 18
  • 17
  • hi I think something is confused here, there is only one window, the values in the window are floats of the last (window size) values. The volume is calculated from the audio output stream of playing music not the user volume, sorry I didnt make this clear. – Thomas Sep 30 '13 at 09:43
  • Well fine, whatever it is, this is one way to go about it. It just depends on the properties (the distribution) of your data, and whether it is critical not to have a small chance of being O(n) "slow" – clwhisk Sep 30 '13 at 20:15