במצגת 19 ב מוצג 'קוד ליצירת גנרטור לראשוניים. אשמח לדעת למה שהתמשנו בסט ולא ברשימה. גם ברשימה אשר לבצע הכנסה בסיבוכיות או של אחד, ולא מתבצע כאן חיפוש.. וגם לא מחיקות
היי, בפייתון משמעותית יותר מהיר לבדוק האם איבר נמצא בתוך סט מאשר אם הוא בתוך רשימה.
בסט הבדיקה היא ב O(1) במקרה הממוצע וברשימה O(n)
אני מניח שזאת הסיבה שבחרו להשתמש בסט.
אריק, ממליץ שתחשוב קצת לפני שאתה עונה נמהרות. לא מתבצעת פה בדיקה האם משהו בסט, אלא עושים איטרציה על האיברים.
לא מעט שאלות זוכות לתשובות לא מדוייקות ממך, אם לא יודעים נא לא לענות.
It's okay to be mistaken sometimes. We are here to learn, and there is no need for such harsh language. Pointing out mistakes without additional personal comments will do the job much better. And for what it's worth, this is the first time I did not agree with Arik on something he posted. Scaring people away from commenting with negativity will do no one any good.
אני מצטרף לאמירותיהם של אריק, עדן גיא ודניאל (ובני למטה).
בקורס שלנו נעלה ביקורת ותלונות באופן מכבד.
checking if the current number is in the list is searching, so set is way better here.
because for checking if element is in the set, complexity is very low-(depends which hash function you use)
but for checking with list we preform O(2^n/n) compares* (n is the input size) with each one with complexity of o(k)(when k is the item size), and you can see that it won't end good for us. and note its not even the worst case.
so please, don't use a list
- see here for estimation the the list length.
I'm afriad that what Arik and Daniel said does not quite apply to this case.
In this code, we use the data structure storing the primes for insertion and iteration. Insertion is O(1) in both lists and sets. Iteration over the items takes O(n) in both lists and sets. In this code, there are no other operations performed on the data structure. The line "for p in prime_set" is a part of the iteration, and has nothing to do with checking whether an element is in the data structure.
Therefore, complexity-wise, using a list is actually equivalent.
One actual reason to use sets is semantics. A set is an unordered non-repetitive data structure, like a set in mathematics, which is exactly what we need. The ordering and repetition features of lists are not useful here, and thus using a set makes more sense.
However, performance-wise, lists are actually more efficient (in both insertion and iteration). I am not talking about the complexity class, but more about the constants involved. I ran the following program with a set and with a list and got the following results:
t0 = time.clock() it = primes() for i in range(10**4): next(it) t1 = time.clock() print('Time Elapsed:', t1-t0)
The results: (average of 10 runs each)
set: 3.67 sec
list: 2.77 sec
So performance-wise, lists are actually preferable!
As I've stated, the only reason to use sets here, is for semantics.
סוף סוף תשובה רצינית, כמו רוב תשובותייך עדן. באמת תענוג לקרוא.
זו גם הייתה מהות השאלה, לפי מה שאני מבין אין הבדל ביעילות עבור הפעולות שמתבצעות בקוד הזה, ולכן לא הבנתי למה שאלו בסוף המצגת למה השתמשנו בסט ולא ברשימה?
בני/אמיר - נשמח לתשובה.
I was under the impression that adding an element to a set will be substantially more efficient than adding it to a list.
This turns out to be a mistake, which I will soon fix.
While at that, I would like to strongly encourage the active participants in the forum to refrain from sharp criticism
on entries by fellow students. Errors are and will be made (by you, by the course staff, etc.). They are essential and unavoidable in any learning process, as well as in research.
If the goal here in the forum is to improve understanding and encourage a true discussion, it is way better to expose errors and suggest ways to fix them without mocking or being negative. We got more than enough of the latter around us in "outside contexts".
Indeed.
For some reason, I belived that we check if something is in the list.
Thank you for pointing out :)
Anyway, a second (and third!) opinion is always great :)
And if i can add one last thing:
I am sure that everyone active in this forum, does its best to assist you, give the most relevant answers he can.
But keep in mind that not everyone is perfect, and we, as well as the course staff will make mistakes.
Be forgiving, help us all.