r/Python • u/sebawitowski • Oct 22 '20
Discussion How to quickly remove duplicates from a list?
417
u/fiskfisk Oct 22 '20
Good points!
Try to avoid posting code as images - it's bad when it comes to accessibility (bad eyesight, etc.), it's bad when it comes to copyability (although it's nice that we're able to emulate the 80s of typing in code from magazines) and it doesn't really work for searching.
63
u/sebawitowski Oct 22 '20
Thanks! I like to use the screenshots from carbon.now.sh because you can immediately skim what this post is about. I would love to include the text version as well, but reddit doesn't allow adding an image AND text together. I tried putting it in the comments, but usually, that comment gets lost at the bottom.
68
u/livingdub Oct 22 '20
It's also not compliant in terms of accessibility. Blind people have no way to access this kind of content, unless you want to dump the whole code snippet in the image metadata.
7
u/CaptainFoyle Oct 22 '20
Are there ways for blind people to code?
58
u/earthboundkid Oct 22 '20
Yes. It’s just text. You just have to be willing to listen to COLON NEWLINE TAB etc
43
u/whoisearth Oct 22 '20 edited Mar 28 '25
beneficial oatmeal edge vanish numerous fear payment wild encourage butter
This post was mass deleted and anonymized with Redact
16
Oct 22 '20 edited Oct 22 '20
You just made me realize that blind people probably prefer tabs rather than spaces.
6
u/MachaHack Oct 23 '20
I have to assume that if editors can make backspace delete a spaces worth of indent, someone should be able to make a screenreader or plugin for one that reads it as "Indent" "unindent" .
I wonder if someone actually has though
0
2
u/Ytar0 Mar 29 '21
Wait, some people indent with spaces? Isn’t that just like, a complete waste of time?
24
17
u/aes110 Oct 22 '20
You'd be surprised how much accessibility has progressed, just google blind programmer blog and you will find many inspiring blind coders
4
u/typewriter_ Oct 22 '20
https://www.youtube.com/watch?v=94swlF55tVc is a great demonstration of how one blind developer works.
-7
u/sebawitowski Oct 22 '20
I would actually love to do that if that's possible. Any idea how to add this? Normally I would use the
alttag, but reddit doesn't support it during submission.81
16
u/Reasonable_Raccoon27 Oct 22 '20
I'd say stay away from images, but if that is your thing, immediately self post the code with a source link (if applicable) and brief description as a comment. That in itself could be a quick scripting project.
5
u/notqualifiedforthis Oct 22 '20
Yes. So this. I like the image popping up in my feed but copy/paste would be nice so immediately commenting on your own post with the code in a code block would be awesome.
2
u/____0____0____ Oct 23 '20
He actually did do that. He posted the image and posted a comment with the link to an article that he wrote. It is just buried at this point, but when I found it earlier it was actually a pretty solid article. I wish that was more up voted so people could see it
4
u/livingdub Oct 22 '20
Not that I know of. I'd just use text instead of images. It's visually almost identical and resolves more than just the accessibility problem.
0
Oct 22 '20
Someone already replied to your higher level comment an hour ago, but the obvious solution here is to just make a Text Post and include the image inside the post body alongside the actual code.
If you're gonna be a developer, you gotta be able to think up obvious solutions like that!
27
u/mikeblas Oct 22 '20
I cant read the text in this post because of the light pirple text on dark ourple background. Are you able to provide an improved version?
68
u/sebawitowski Oct 22 '20
Sure thing, here is the code from that image in a text form:
# Let's make some duplicates from random import randrange DUPLICATES = [randrange(100) for _ in range(1_000_000)] # Not very efficient unique = [] for element in DUPLICATES: if element not in unique: unique.append(element) return unique # Very efficient list(set(DUPLICATES)) # This works because sets contain unique items by definition # But sets are unordered! What if we need to preserve the order? # Use this dict.fromkeys() trick! list(dict.fromkeys(DUPLICATES)) # But it only works for Python 3.6 and above # For Python 2.7 and 3.0-3.5, use OrderedDict: from collections import OrderedDict list(OrderedDict.fromkeys(DUPLICATES))12
u/mikeblas Oct 22 '20
Thanks! That's immensely more readable, and I can control the colors or use my screen reader. I can't understand why anyone would prefer the horrible colors in the original post, particularly at the cost of excluding people.
Any the original text couldn't be copy-pasted anyway, which is the first thing you usually want to do with code, right?
Anyway: this implies that Python 3.6 and newer use
OrderedDictby default; and thatOrderedDictpreserves the insertion-order of keys. Is that true?4
u/sebawitowski Oct 22 '20
I can't understand why anyone would prefer the horrible colors in the original post, particularly at the cost of excluding people.
I see your point, and I wish reddit would provide some better tools for alt text of the image or at least let me link text and image together. Or if it would at least provide some color highlighting to the code in posts. In the past, I tried adding a comment with the code from the image, but it immediately got lost among other comments. I like small code snippets like this presented in the form of an image. They are much easier to quickly skim what they are about when you are just scrolling through reddit. And I'm afraid that most people like them too - I've posted the same tip to r/pythontips with just pure text, and it got no attention (I know that this subreddit is much bigger, but still). I will try to include code in comments in the future. I hope it helps a bit!
Anyway: this implies that Python 3.6 and newer use OrderedDict by default; and that OrderedDict preserves the insertion-order of keys. Is that true?
Actually no, Python 3.6 changed the implementation of the dict() to be more efficient, and keeping the insertion order was a side effect of this. In Python 3.7, keeping this insertion order was officially guaranteed in the documentation.
8
u/xnign Oct 22 '20
I actually like the colors and formatting. Memes are transcribed all the time... All you need to do is paste it in the comments in a code block, or as a link; you don't need to force 100% a11y all the time, a transcription in the comments is plenty.
Thanks for sharing. I may make a few PRs to that Carbon site's repo.
6
u/Vhin Oct 22 '20
It's perfectly legal on reddit to add links in a text post. Multiple links, even, so there's no need to choose between the two.
And in any case, if you really had to choose between the two, always go with the text version, unless you're just showing off your terminal's theme in something like r/unixporn. It is immensely more useful.
This goes especially so if you're asking for help, because often people will need to copy at least part of your code to answer your question. Would you want people to have to retype your code manually just for the sake of having it show up in pretty colors?
If someone really cares about the colors, having the text means they can quickly copy-paste it into their editor of choice with their theme of choice and look at it.
2
u/mikeblas Oct 22 '20
In Python 3.7, keeping this insertion order was officially guaranteed in the documentation.
Thanks; that's what I was after. Maybe it's a happy side-effect, maybe it's guaranteed. We want it to be guaranteed for usages like this.
1
u/wnoise Oct 22 '20
What's wrong with posting it just as a link to a gist on github or wherever? Gets nice formatting and syntax highlighting, still easily copyable, etc.
2
3
u/scrdest Oct 22 '20
Anyway: this implies that Python 3.6 and newer use OrderedDict by default; and that OrderedDict preserves the insertion-order of keys. Is that true?
OrderedDictalways preserved the insertion order, that's the whole point of it.The new
dictsare NOT the same things asOrderedDicts.OrderedDict's niche now is re-ordering its data - kind of likecollections.dequecan be viewed as a variant of alistthat is optimized for modifying data at either end.So, for example, if you were writing something that tracks jobs, pops, updates the job key with the timestamp of last refresh as a value and puts them back on the end of the queue -
OrderedDictwould probably be a good design choice.1
1
u/Brian Oct 24 '20
Eh - a regular dict would work just as well as OrderedDict for that usecase. Both are going to maintain insertion order, even after removal and re-insertion.
There are some differences between OrderedDict and regular dicts, but they're not anything to do with re-ordering data. Rather, the main difference is that OrderedDict treats order as being important for things like equality comparisons. Ie.
{1:1, 2:2} == {2:2, 1:1}, but the same is not true for OrderedDicts.49
u/LazaroFilm Oct 22 '20
It's such a shame that Reddit doesn't support color coding like GitHub.
2
u/zacharypamela Oct 22 '20
Or SO.
5
u/LazaroFilm Oct 22 '20
SO
I'm not sure I understand what you mean...
17
u/0xh4ck3r Oct 22 '20
Stack Overflow
3
u/zacharypamela Oct 22 '20
That's the one.
10
u/jadkik94 Oct 22 '20
For the longest time people were using SO as Significant Other on random posts on reddit and I only knew it as StackOverflow.
I never bothered to Google it, just brushed it off as a weird reddit thing at the beginning :D
→ More replies (0)2
1
4
u/oh_lord Oct 22 '20
Maybe just throw a
(code in comments)to the title so people who need that option know to look for it.Alternatively, you could post it as a self-link with the image in there and the code duplicated (behind a spoiler tag if you wanted it to be more succinct).
4
u/mishugashu Oct 22 '20
reddit doesn't allow adding an image AND text together
Yes it does. Do a text post, and add images using their WYSIWYG editor. It'll post the image in-line. Note this only works for posts, not comments. You also have to be on the "new" reddit to see in-line. Old reddit clients will see a link.
2
2
u/zanfar Oct 23 '20
It's also not searchable, copyable, or scalable. It's 104,000 bytes instead of 570 bytes, and doesn't reflow on a mobile device.
What's the point of teaching someone something if they can't experiment with it?
I also don't agree that the image provides any benefit for "skimming".
1
1
7
1
u/miciomacho Oct 23 '20
Right. However, it is very pretty. How would it sound posting image and plain text in comments?
1
u/lazerwarrior Oct 22 '20
Images are probably posted because they get picked up by the algorithm for upvotes
6
u/larsga Oct 22 '20
There is no algorithm. Images float up because the new reddit layout favours image content. People see the image right in the toplist and upvote it without ever entering the post. It's easy, so it gets more upvotes.
-4
16
u/ProcyonRaul Oct 22 '20
unique = sorted(set(DUPLICATES), key=DUPLICATES.index)set gets you the unique elements. sorted gives you a sorted list. key tells sorted exactly how you want things to be sorted. index is a string method that returns the zero-based index of where the character you're searching for first appears in a string. (Other data structures like lists have an index method, too.)
Put all together, this one-liner says to find the unique items in DUPLICATES and put them in a list ordered by where they first appeared in DUPLICATES.
Edit: put in markdown mode.
10
-1
6
u/OXKoson Oct 22 '20
Does anyone actually know what set is doing in the background to run so fast? is it just some kind of sorting algorithm that removes duplicates as it goes?
22
u/AnythingApplied Oct 22 '20
is it just some kind of sorting algorithm that removes duplicates as it goes?
Nope, it's actually FASTER than that. Have you ever run into the error when trying to put a list into a set or use a list as a dictionary key: "TypeError: unhashable type"?
What sets and dictionaries do is create something called a hash table. Each element gets a hash calculated for them, which turns the object into a number (but importantly you'll always get the same number for any equal objects), and then that number is used to figure out where in memory to store that object. This is why mutable objects like lists can't be hashed because if they have their values changed, it would need to update where in the hashtable they're stored.
So when you add a new object, it first hashes them, and then using that hash it knows exactly where in memory it should look to find a potential duplicate.
With lists, checking for a member is a O(n) operation, for sorted lists you can use binary bisects, which is O(log n), but for hash tables it is essentially O(1).
Though, multiple objects can end up on the same location in the hash table, especially for a small hash table, so it isn't always O(1).
https://www.geeksforgeeks.org/internal-working-of-set-in-python/
3
4
3
Oct 22 '20
Unordered sets are based on hash tables. So I think in the first method where the line
if element not in unique:this can be worst case O(n) and it is reduced to O(1) due to hash table.
2
Oct 22 '20
To be more specific about implementation, Python uses open addressing.
Read the source code if you're interested (and can read C)
https://github.com/python/cpython/blob/master/Objects/setobject.c
2
Oct 22 '20
Python’s implementation of sets and dicts relies on the hash() function, but it’s useful to know that its actually a pre-hash function. The order of events is:
Take an immutable object and apply hash() to it. This generates (for non-integers) a very large number, you can try this in an interpreter. For integers, hash() just returns that integer.
Now (and this is hidden from the user), you use a hash function (not hash()! but hidden Python internal hash functions) to map that very large number produced by hash() to a memory address, which can be accessed in constant time (due to the hardware using (more-or-less) random-access memory hardware).
Repeat this process every time you add new elements to your dict or set.
This gets very complicated very quickly, because good hash functions (that produce a uniform distribution of output, so there are no hash collisions, and memory is efficiently used) are hard to come up with. Here’s a nice introduction to the world of hashing in Python, courtesy MIT Press:
https://planspace.org/20150111-a_great_python_book_explains_hash_tables/
Also, see the MIT online lectures on hashing (in Python), which discuss why hash() is really pre_hash(), they were very helpful in learning the concepts, here’s a link plus transcript:
https://learn.saylor.org/mod/page/view.php?id=19006
Python does all this work for you under the hood, but knowing a bit about how it works will make you a more confident programmer. If you really want a glimpse into the truly gory details, yikes, here you go, a 2013 discussion of the under-the-hood hash functions used inside Python:
1
u/OXKoson Oct 22 '20
Agreed this kind of low level info is super helpful without this I would have made my own serviceable implementation(nowhere near O(1)) assuming the built in one was bad or didn’t exist.
4
u/rxsteel Oct 22 '20
How does one learn this trips and tricks ? Is it just time and exposure to python code ?
11
u/sebawitowski Oct 22 '20
For me, yes - time and solving a lot of different problems. Once you google for "remove duplicates in Python," you will quickly find this answer, and you will probably remember it forever. I hesitated if I should even write this post because I thought: "probably everyone knows that!".
I didn't study computer science, but I believe there you learn that sets are unique (although, probably not many people remember this theory after university ;). Also, in this specific case, a math background helps.
A good way to practice this is to solve some simple code problems (code katas), for example, on this website: https://www.codewars.com/. Once you solve a given problem, you can check the most upvoted solution and find a much more efficient way to do this (at least, that was my experience :P ).
1
-1
u/khne522 Oct 22 '20
but I believe there you learn that sets are unique (although, probably not many people remember this theory after university ;)
Uh, you learn a lot more, and not in some shallow fashion if you pay attention in class (cough some classmates). AFAIK you don't also just forget most of it or trivial and easy things to remember like that unless you're seriously demotivated or mediocre.
2
u/khne522 Oct 22 '20
Time and exposure aren't guarantees, and they mean you learn a fixed set of “trips” and tricks. It's a less predictable outcome “trip”, with likely lower long-term value.
A good degree or series of courses in the basics.
Meaningful practice during those courses.
Motivation. Desire for excellence. I.e., ¼ of my classmates, even at last chance U.
Reflection, and not the programmatic kind but seeing implementation and design patterns, appreciating their abstract qualities, theoretical or practical, etc. A good scientific mindset.
Reading the relevant parts of the darn docs sufficiently thoroughly. If you read them and either practice or have a good memory already, of all the basic parts of the Python language, then expressing yourself in a cool fashion like that is easy. If you learn hackily, that's on you.
Mentorship under the right people unless the most hardcore bootstrapper, in which case good, modern, curated literature helps. Good luck finding a syllabus though.
Ability to properly formulate the problem and then put two and two together, or rather, a bit more. Want sub-O(n²) time order and type-preserving duplicate filtering but at what scale? sub-10k? A million? How much RAM? What operations can you add or multiply by such that you stay under O(n²) for acceptable RAM or disk usage? Remember what you have available then try and put it together.
Learn the lingo, so that you not just express yourself concisely, but you can think concisely.
Exposure only works if it's the right one. If you learn under somebody who teaches and writes Python like it's JS/C/Java from 2005, you'll be hampered by how they only express themselves the way those languages do.
There is no magic shortcut. Don't go looking for one. At best you'll find yourself an expert in canned answers to a specific set of problems. You'll also not likely have learned how to learn properly.
1
u/khne522 Oct 22 '20
Part of reading the docs means internalizing things like:
You probably won't find all of these, much less referenced, in your time reading other peoples' code or blogs. I.e., you won't have coverage.
1
1
u/yaxriifgyn Oct 22 '20
How does one learn this trips and tricks ? Is it just time and exposure to python code ?
You have to go old school and actually read the the manual that comes with Python, or go to Python 3.9.0 documentation.
-6
u/Barafu Oct 22 '20
It is obvious if you read the Python documentation instead of all those "learn Python in 1 minute" books.
2
u/rxsteel Oct 22 '20
How do you commit all that info to memory? That documentation is long.
12
u/SupahNoob Oct 22 '20 edited Oct 22 '20
Simply put, they don't, that's some reddit persona gatekeeping bullshit.
You won't learn the dict / OrderedDict variants of deduplication in the docs. That comes with Google-fu or having an innovative understanding of the data structures.
Learn a few things, commit them to memory, put them into practice. They'll eventually become second nature as tools in your tool belt. Then you go and learn something new to add to your belt.
e.g. a natural progression might look like
sets are unordered unique collections
I can convert other collections to a set with
set(...).. commit to memory, some time passes ..
3. learn
dict, understand thatdict.keysmust be unique.. hey wait, can I use 3 and 2 together somehow? ..
4. research and find
dict.fromkeys, combine with knowledge of 3 and 2.Now you've got a few algorithms in your head to remove dupes from a collection.
1
u/NoblySP Oct 22 '20
This is not related to the thread but what does "Google-fu" mean? Is that an acronym for something?
2
u/SupahNoob Oct 22 '20
Ha ha, it's a informal term which essentially means "your skill in using Google" aka how well you can [ab]use a search engine to find the information you're seeking.
Google kung fu.
1
u/anizotropia Oct 22 '20
Experience in general. But there's no way someone "commit all that info to memory". :D We learn by doing it everyday, solving problems, code reviews, reddit discussions... I think that studying is helpful but not necessary.
69
u/Aardshark Oct 22 '20 edited Oct 22 '20
If you used a set in your loop example, then it would perform well and retain order.
def uniques(duplicates):
unique = []
seen = set()
for element in duplicates:
if element not in seen:
unique.append(element)
seen.add(element)
return uniqueFrom my tests, this actually performs better than the OrderedDict implementation in Python 2.7 and 3. This is particularly true on Python 2.7, where it runs in about 1/15 of the time.
14
26
u/achampi0n Oct 22 '20 edited Oct 22 '20
I'm not recommending this but you can use a simple trick to do this in a list comprehension which might have a very minor performance improvement:
def uniques(duplicates): seen = set() return [seen.add(elem) or elem for elem in duplicates if elem not in seen]Because
seen.add(element)always returnsNonethenelementis evaluated and used as the result for the list. Ugly, I know :)9
u/sharkbound github: sharkbound, python := 3.8 Oct 22 '20
that is quite clever, i did some timing and this is the results:
this is the code used to test it:
from time import perf_counter_ns def timed(func): def timing_wrapper(*args, **kwargs): start = perf_counter_ns() ret = func(*args, **kwargs) diff = perf_counter_ns() - start print(f'{func.__name__} took {diff} NS to run') return ret return timing_wrapper @timed def remove_duplicates_list(values): seen = set() return [seen.add(value) or value for value in values if value not in seen] @timed def remove_duplicates_set(values): return list(set(values)) print(remove_duplicates_list([1, 2, 6, 1, 7, 1, 9, 4, 2])) print(remove_duplicates_set([1, 2, 6, 1, 7, 1, 9, 4, 2]))results:
remove_duplicates_list took 3200 NS to run [1, 2, 6, 7, 9, 4] remove_duplicates_set took 1900 NS to run [1, 2, 4, 6, 7, 9]these timings where pretty consistent, not deviating too much
EDIT: should note that this is to just show the diff between list of set conversion vs the "ordered list comp set" way
3
u/achampi0n Oct 22 '20
Cool, thank for the timings. The one difference being it manages to preserve order.
4
19
u/SherlockPotato Oct 22 '20
Is 1_000_000 the same as 1000000 here?
32
u/pepoluan Oct 22 '20
6
4
u/Klaus_Kinski_alt Oct 23 '20
Very helpful, I had no idea that's legal.
Note also that you can have commas in printed outputs very simply with F-strings.
var = 1000000
print(f'{var:,}')
This will get you 1,000,000.
10
4
1
u/random_____boi Oct 22 '20
Beginner here, what is _ used for?
3
u/sebawitowski Oct 22 '20
It's a convention for a throwaway variable. You use it when you need to use a variable, but you don't really care about it (in this case, I need to use a variable in a list comprehension, even though I don't do anything with this variable) - keep in mind that this is not a good use of a list comprehension and I used it only as a quick hack to generate some numbers. But it's just a convention, you might as well use "i", "a", "x" or "a_throwaway_variable" as you prefer :)
Here is a better explanation: https://stackoverflow.com/questions/36315309/how-does-python-throw-away-variable-work
1
u/HAVEANOTHERDRINKRAY Oct 22 '20
_
also a beginner. someone come down and correct me
The first one is just OP's variable that they set... It's the same as using i, or any other variable. In the 1_000_000 value, python is able to read that as a value separator (basically so your brain can comprehend where we would usually write commas)
1
2
2
u/blablafoof Oct 23 '20
Beginner coder here.
How can you tell which method is more/less efficient compared to other different types of methods?
1
1
u/arthur_olga Oct 22 '20
Depending on the case you can actually juat use set() if you don't need to have any special property of a list
1
1
1
u/oxlade39 Oct 22 '20 edited Oct 22 '20
If in your not very efficient example you also had a set of entries and always added to that but only added to the list if the entry doesn’t already exists in the set wouldn’t that be more computationally efficient (but obviously not more memory efficient)
1
1
1
1
1
u/JR4smus Oct 22 '20
I really like this colour theme is it available for Vs code? If it is a link would be appreciated
1
1
1
u/Myst3r10 Oct 22 '20
More of a beat standards question....
Why don't people use multi line comments rather than multiple #?
Is there a specific reason for avoiding multiline?
1
u/execrator Oct 22 '20
There are no multiline comments in Python. If a string (including multiline strings) is the first statement in a module, function or class it will be used as the docstring. Outside of the first statement you are just writing a string literal without assigning it.
1
u/Myst3r10 Oct 22 '20
I've used the following to comment out large chunks of code
''' Comments here '''
Is this not a multiline comment? Or is this something different?
2
u/execrator Oct 23 '20
That is a multiline string :) You can prove this to yourself by assigning it, which wouldn't work if it were really a comment:
text = '''Comments here'''Pragmatically speaking, it can still stop a block of code from running so no harm in using it while you're debugging something.
1
u/Myst3r10 Oct 23 '20
Hot dang. Learned something new today. Now I need to go test it out!
Thanks for the info!
1
1
u/RBGForever Oct 22 '20
I definitely thought it said dict.formonkeys(). Now I'm a little bit disappointed and suspecting myself of having dyslexia
1
1
1
1
Oct 23 '20
If an order doesn't matter (aka unstable):
unique = list(set(DUPLICATES))A stable version will be:
def stable_unique(it):
seen = set()
for i in it:
if i not in seen:
yield i
seen.add(i)
unique = list(stable_unique(DUPLICATES))This will return each value in the order of their first appearance.
You can remove list(...) if you are just iterating
1
u/anonymous-x-31 Oct 23 '20
I would do this:
listA = [1, 2, 13, 4, 16, 2, 3, 4, 1, 1]
listB = list(dict.fromkeys(listA))
Doing that will convert the list into a dict first, which doesn't allow duplicates, so that's how I'd go about removing the duplicates
1
1
Oct 23 '20
i see these type of screenshots all the time. can someone please tell me which framework or IDE the code is written in? its sure not pycharm and sublime.
1
1
u/Z_Zeay Oct 22 '20
Can I ask how you made the picture? I remember someone sharing a plugin/site of some sorts that you can make these images quickly with code snippets.
1
u/muffinnosehair Oct 22 '20
I found this solution a few weeks ago, it was a life saver. Very useful tip.
1
1
u/mobsterer Oct 22 '20
or just this:
set(listA)like this:
>>> listA = [1,2,3,4,5,6,7,8,9,0]
>>> listB = [7,8,9,0,11,12]
>>> listC = listA + listB
>>> print(listC)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 7, 8, 9, 0, 11, 12]
>>> print(set(listC))
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12}0
u/Sigg3net Oct 22 '20
If the list is huge (or endless) you're going to have a problem. You need to add a generator alternative using the yield keyword to your list.
0
0
u/T-ROY_T-REDDIT Oct 22 '20
Funny thing, I actually coded something similar with the pandas package.
0
u/primitive_screwhead Oct 22 '20
unique = []
seen = set()
for element in DUPLICATES:
if element not in seen:
seen.add(element)
unique.append(element)
return unique0
u/nekokattt Oct 23 '20
The containing check is kind of redundant, since add will do the same hash check internally anyway, if you used a dict with none values, you'd get the same effect.
1
u/primitive_screwhead Oct 23 '20
And how would that keep the redundant elements out of 'unique'?
1
u/nekokattt Oct 23 '20
because dicts can only have unique keys, and retain insertion order.
You just save doing 1 million unnecesarry hashes of values, which will begin to have a noticable overhead
1
u/primitive_screwhead Oct 23 '20
I'm not using a dict at all.
1
u/nekokattt Oct 23 '20
im saying you could use a dict as shown and it would be equally effective, and more efficient, other than space complexity. But you are likely going to hit a similar issue with keeping a set and a list anyway.
Another interesting alternative is to use the bisect module from the standard library if you also wanted the results sorted as you process them.
Or you could use a heapq.
0
u/primitive_screwhead Oct 23 '20
I'm specifically showing a canonical approach (used across multiple languages, actually), that doesn't rely on whether a dict retains order or not. It's a contrast to the dictionary approaches that were already shown by the OP.
1
0
u/drbobb Oct 23 '20
Presenting source code as pictures seems to be all the rage right now. I personally regard it an aberration.
-3
u/FrozenPyromaniac_ Oct 22 '20
Use a set, it shows only the unique values in a list, then make a list out of the set
For example let’s say your list is L = [a, b, c, c , d, d, d] (assume all letters to be strings, I’m on mobile) let the set be initiated like this S = set(L) , it will have a output like this {a, b, c, d} (not that this set may be out of order, you may have to sort the list if it’s important ). Finally make the list L = list(S)
Note this is very simplistic method
2
u/nuephelkystikon Oct 22 '20
The entire point of the post is that this doesn't work if conservation of order is important.
Sorting the entire list after the fact is incredibly inefficient, and may not be trivial if the order doesn't directly follow from the data.
1
-2
Oct 22 '20
JavaScript with one line:
const unique = [...new Set(dupes)]
edit, this is only useful for primitives
-2
u/Astronom3r IPython > Jupyter fight me. Oct 22 '20
unique = numpy.unique(list)
If you're looking for a one-liner.
-3
-3
0
Oct 22 '20
[deleted]
10
63
20
17
31
8
u/AzureWill Oct 22 '20
Not a good idea IMO as you will lose the order. Use a dictionary and you'll be fine.
-11
u/miguendes Oct 22 '20 edited Oct 22 '20
T̶h̶e̶ ̶c̶u̶r̶r̶e̶n̶t̶ ̶d̶i̶c̶t̶ ̶i̶m̶p̶l̶e̶m̶e̶n̶t̶a̶t̶i̶o̶n̶ ̶d̶o̶e̶s̶n̶'̶t̶ ̶p̶r̶e̶s̶e̶r̶v̶e̶ ̶o̶r̶d̶e̶r̶.̶ ̶S̶o̶ ̶t̶h̶e̶ ̶o̶u̶t̶p̶u̶t̶ ̶w̶o̶u̶l̶d̶ ̶b̶e̶ ̶t̶h̶e̶ ̶s̶a̶m̶e̶ ̶a̶s̶ ̶u̶s̶i̶n̶g̶ ̶a̶ ̶s̶e̶t̶.̶ ̶I̶n̶ ̶t̶h̶i̶s̶ ̶c̶a̶s̶e̶,̶ ̶I̶ ̶w̶o̶u̶l̶d̶ ̶r̶a̶t̶h̶e̶r̶ ̶u̶s̶e̶ ̶a̶ ̶s̶e̶t̶ ̶f̶o̶r̶ ̶t̶h̶a̶t̶.̶
Edit: I'm so dumb, I misunderstood the feature completely. I was thinking about the natural order of the keys, not the insertion one. Sorry about that!
0
Oct 22 '20
[deleted]
2
u/cryo Oct 22 '20 edited Oct 22 '20
That’s IMO a weird thing to lock yourself into, but whatever. For comparison, in .NET they also preserve insertion order, until deletion, and pretty much always have, but this isn’t guaranteed. In Swift, it uses a hash table with open addressing and linear probing, also with no guarantees.
2
u/grnngr Oct 22 '20
Is it specified which duplicated element to keep? For example, if I have a list
[4,0,1,2,3,4], am I guaranteed to get either[4,0,1,2,3]or[0,1,2,3,4]?2
u/NoLemurs Oct 22 '20
The documentation isn't explicit on this, so I think technically it's an implementation detail that you shouldn't rely on.
In practice, I would expect
[4, 0, 1, 2, 3]every time. The natural implementations here are either to insert every key as you encounter it (overwriting as you go), or to only insert if the element isn't present. Either way, as /u/colemaker360 pointed out, if you don't remove the element, the initial insertion determines the order.2
u/grnngr Oct 22 '20
The documentation isn't explicit on this, so I think technically it's an implementation detail that you shouldn't rely on.
That’s why I asked. Presumably if preserving the order matters to you, you’d also care about which of the duplicated elements is preserved.
2
u/nitroll Oct 22 '20
Order preservation in dictionaries is defined, but it is not so for sets "Being an unordered collection, sets do not record element position or order of insertion." All behaviour observed is thus an implementation detail.
7
u/colemaker360 Oct 22 '20 edited Sep 13 '25
connect glorious squash axiomatic recognise fade alleged spoon serious lock
This post was mass deleted and anonymized with Redact
1
u/anyonethinkingabout Oct 22 '20
And usually you dont even need to make it a list again
1
u/iiMoe Oct 22 '20
I've seen some basic exercises that happened to insist on the form of data but regardless i totally agree you can just keep it a set
-4
u/Saviour2401 Oct 22 '20
Same
-15
u/iiMoe Oct 22 '20
Senior devs think alike
2
0
Oct 22 '20
[deleted]
8
u/jwink3101 Oct 22 '20
Yes!!! This is what I was thinking. Functions and other programing behavior should be thought of as a contract. You give me this and I'll give you that.
In CPython 3.6, dictionaries respected insertion order as a bonus but it was not part of the "contract" with the API. Python 3.7+ made it part of the contract and now you can rely on it.
For anyone else reading this though, I wrote this PSA a few months ago about ordering and equality. The TL/DR is that
OrderedDictscare about order for equality while regular dicts, regardless of python version, do not0
u/cbarrick Oct 22 '20
Didn't Python 3.6 promote the ordering from an implementation detail to a guarantee? Or was that 3.7?
In any case, the Python language guarantees that all dicts are ordered these days.
0
Oct 23 '20
[deleted]
1
u/sebawitowski Oct 23 '20
It's just a syntactic sugar that makes counting zeros much easier.
1000000and1_000_000are equivalent in Python.
0
Oct 22 '20
[deleted]
1
u/aggressive_sigh Oct 22 '20
sets are unordered. the next option in the post explains what to do if you need to preserve order
0
0
0
38
u/sebawitowski Oct 22 '20 edited Oct 22 '20
And this simple one-liner is (probably unsurprisingly) an order of magnitude faster! You can find the benchmarks in this blog post: https://switowski.com/blog/remove-duplicates
Also, something important to keep in mind (that I forgot to include in the original image) is that this only works for hashable elements on the list. If you have a list of lists, sets, or dictionaries, you can't convert it to set and you are left with the "ugly" for loop.