Finding the lowest number with O (1) runtime - java

Question

I need to create a data structure based on Linked list, Array and read-only memory.

As input, I get two numbers: N and M.

N represents the maximum disk capacity per key, M represents the maximum capacity of the computer’s hard drive, so M> N.

Therefore, I need to create a program that "transfers" information from the hard disk to disk-to-key. This program should implement the following methods:

• Insert (data) - Inserts data into a disk-on-key, if it is full, it deletes the data of least importance (*): the worst execution time is O (1).
• delete (data) - deletes data from disk to key - O (1)

(*) user can change the value of the file.

Maximum Memory Usage - O (M)

What i have done so far:

I created an array [1 ... M] that will "hold" the computer data, I created a doubly linked list in which data will be stored on disk. [The idea is this: every time the data is added to disk-by-key, they will be added to the linked list, and I can go directly to the data using the array as an index (/ key) storage.]

My computer data fields:

node firstNode; node currentNode; node[] dataCollection; // Will hold computer hard-drive data 

So, I wanted to create a method that replaces the least important data with the data I want to add [so that I can use it in Insert], My code to replace:

 public void replace(int leastImportantdata, int insertData){ node leastImportant = dataCollection[leastImportantdata]; if (leastImportant.prev!=null) leastImportant.prev.next=dataCollection[insertData-1]; if (leastImportant.next!=null) leastImportant.next.prev=dataCollection[insertData-1]; numOfReplacements++; 

So, my main problem is finding the least important data considering these two “combined” data structures and still preserving the O (1) runtime, especially when the user decides to change the importance of the files.

• Suppose we start with {4,3,2,1} (numbers are important) the least important data will be 1. Suddenly, the user decided to change the value of the last file to 5, we get {4,3, 2,5}, and the least important data - 2.

Any idea?

Answer 1

To be able to determine the least important data, you need an order on your list.

So, does that think whether ordering a linked list at all? you seem to be getting data based on the index, and not by moving through the list. (If this order matters, the rest of my answer may not be very useful: D).

This means that you can insert items into the list so that they are sorted in order of lowest priority, which would allow you to get the item to be deleted with constant performance, if you have a link to the head of the list,

This, unfortunately, makes insertion difficult. To fix this, you can save the priority map to the last (and potentially first) file in a linked list with that priority.

Using this card, you can instantly determine where a new file should be inserted, thereby ensuring consistent performance.

so if you have 3 files P (A) = 1, P (B) = 3, P (C) = 3, your map will look like 1 → (A, A) 3 → (B, C), saying that if you want to insert another file with priority 1, it must go after A and if you want to insert a file with priority 2, it must go to B.

Obviously, I assume a finite number of possible priorities here and that there are no gaps between the priorities used. (which will require a search)

Hope this helps

Answer 2

My suggestions for solving your problems:

• Define a node class to implement the Comparable interface.

• Embed data collection in the skip list - you can do this using ConcurrentSkipListMap .

Using the SkipList implementation can ensure that entries are ordered by their importance.

According to the Java API. This class ( ConcurrentSkipListMap ) implements a parallel version of SkipLists, providing the expected average time log (n) cost for containsKey, get, put and remove operations and their variants.

In the general case, the implementation allows you to search for elements with an efficiency comparable to balanced binary search trees (that is, with the number of probes proportional to log n instead of n ).

Finally, see [here] for more information on SkipList and how to write your own implementation.