Java List O(1)
Images are sometimes not shown due to bandwidth/network limitations. Refreshing the page usually helps.
You are currently reading a thread in /g/ - Technology
You are currently reading a thread in /g/ - Technology
Is it possible to modify a list data structure so that access, search, and insertion are all O(1) time?
>>51865644
lol is that your homework? Your prof is a retard
>>51865672
That seems to be the consensus
Amortised? Sure just use a hash table
>>51865644
I don't think it would be a list anymore.
>>51865725
Add wouldn't ALWAYS be O(1) if it becomes full, also >>51865755
>>51865644
> Search
> O(1)
> List
Nope.
>>51865821
>Add wouldn't ALWAYS be O(1) if it becomes full
mate do you even know how lists work? they don't get full you idiot
>>51866149
fuck off code monkey
>>51866198
then enlighten us on how a fucking list gets full.
The only thing full is your head and it's full of shit
>>51866220
>>51866149
Hash tables get full, idiot.
>>51866227
oh my bad mate, you were replying to the other guys post.
In light of this, I am sorry
>>51865644
>access, search, and insertion are all O(1) time?
Hash tables can do this but it isn't always O(1) time though. It all depends on the hashing algorithm and where data gets stored in memory.
>>51866280
Think nothing of it
Use a hash table.
Though it's not always O(1).
With collisions, it may take O(n).
>>51865644
It doesn't say you need search to do O(1). But yes this assignment is easy as shit and possible. Congrats on your first semester of CS.
To everyone else in the thread, the pic does not say that search needs to be O(1)
>gets
>puts
>add
That's it
>>51866227
>What is resizing dependant on load
>>51866395
Good point. But isn't add for putting at a specific position? That would create the same problems as search.
>>51866452
It's more likely that put is at a specific position, and add is at the end, but yes
>>51866395
get:
for O(1) to work 100%, you can use an array/list. A hash table worst case scenario is O(n) although very unlikely. This depends on the data, the hash function and amount of memory allocated.
put:
Putting data in arrays/lists can put data in O(1) time. Hash tables usually work in O(1) but can go up to O(n) as well.
>>51866452
Not for this problem, no. This is a typical first semester CS end of year problem. Add usually is implemented as a queue or push type procedure and usually doesn't require shifting elements left or right.
>>51865644
Linked lists are aids and cancer.
Pretty much don't use them ever. Entries will be all over the place in memory so you'll get constant cache misses.
Just forget they exist.
>>51866220
>then enlighten us on how a fucking list gets full.
you run out of RAM (or rather resources allowed to you by virtual machine, because Java)
>>51866562
>I never learned proper memory management
>>51866632
not that guy but what the fuck are you going on about? he's right.
>>51866296
hash tables aim on average complexity, they are shit for worst case complexity.
>>51866395
Get isn't the same as search?
>>51866562
The Linux Kernel uses a lot of linked lists/doubly linked lists for process/threads/schedules - eg. thread_info, task_struct (the process control block) is a large circular doubly linked list
>>51866569
those are two completely different problems...
>>51866648
one should link large enough arrays, so they avoid cache misses mostly but you have good asymptotic complexity too. There are efficient linked datastructures, look at btrees.
>>51866716
Take an array for example:
A = [2, 4, 1, 5, 7, 8]
If I were to do the operation: A.search(5) it would require me to do a linear search for this, looking at the first element to the last element.
If I did a get operation, I'm getting the position of the array, which takes O(1). For example A.get(5) would return the value 8.
>>51866773
he said "don't use linked lists" and I don't see you raising any points against that
>>51866794
True, cache locality totally depends on the allocator though. If one writes a specific allocator tuned for linked lists it could make a difference. I have no experience if this idea is worth pursuing though,
>>51866852
well yeah maybe. I suppose you could make an architecture optimal for linked lists too. but it's better to stick to the things that we currently are actually using when discussing performance
>>51866793
Thanks man
>>51866890
It's not that low level, even C++ lets you write a custom allocator. I think it's not impossible to write a linked list class with a custom allocator that makes the a data structure somewhat cache efficient.
>>51866505
So the design would be to use an array list for get and put.
>>51866539
Add would be used as a queue?
I'm trying to think how this all comes together as a single implementation since I'm having trouble with the idea of it.
I'm not trying to write it out as code, just how the algorithm would work.
>>51867135
If you are OP, ask the professor what the fuck he is asking for
>>51867187
The "design". For example,
A chained hash table is an array of pointers to linked lists of nodes with a key and value. Get(k) calculates the hash code and then hash index of k and then looks for the node in the list at that index for the one with that key.
>>51865644
Sure, Just limit the maximum number of elements in the list to 1?
Individually? Sure, to an extent.
You can't have both "get and put are O(1)" and "add is always O(1)" at the same time, but it seems like your prof actually wants two separate implementations.
>>51865644
/g/ has taught me a lot over the years so I can say that of course, and it's really easy!
First, you need to solve P = NP. With P = 0, we prove that P = NP so that's good. Then you have to reduce the graph isomorphism problem to a search, access or insertion problem. That, too, is easy. All you have to do is put the target node first in the isomorphic graph and there you go.
Thus, it's trivial to perform such an operation.
>>51866736
Not to mention the entire notifier ideology.
>>51866562
Linked list are literally the single most important data structure in CS (if you consider arrays to not be a data structure as it's merely a contiguous block).
