In problem 4, we’ve given a list of n numbers
and our task is to find the mode, within time
Theta (n). And there’s a lot of different ways to
do this and – so, what I’ve done is, I’ve gone
through and basically written five different ways
of doing it. All variations of the theme really. In
the first case, what we’re going to do is, we’re
going to use a dictionary and when we iterate
through the dictionary, keeping track of the
element that has been seen the most often. So,
here we’re just doing initialization, if we haven’t
seen this value before we’ll create a key value
pair and set its value to 1. If we have seen this
key – this value before, we’ll just increment the
value associated with it. As we’re going along,
we can keep track of what the value – what
value we’ve seen the most. So, if the value that
we’ve just updated is higher than the previous
maximum value, we will set the current
maximum value to be this current key value
pair. As a result, by the time we finish this loop,
which is 1 pass through the list, we will know
the mode or we’ll know one of the values in the
mode, if there’s more than one value that has
the same number of appearances and we’ll just
return that. There’s a lot of different ways you
can do this and a slight variation of that, that
let’s us shorten our code a little bit is when you
can use the default dictionary that Python has.
And what we’re doing here is, we’re saying
basically that the first time you see a key, you’re
going to give it an initial value using this int
function, and it’s going to give it a value of zero.
So what that allows us to do, it lets us get rid of
this little bit of code here, that check to see
whether or not the value existed already, which
is a single look-up in a hash table basically. So,
what we do now is we just increment the value
by 1 regardless, and so the first time it sees it,
it’ll use the default dictionary value of zero, add
1 to it and give us the value of 1, so it’s
basically the same as what we’ve done before.
And the rest of the code is the same, just
keeping track of the maximum value and
returning it. Another thing you could do is you
can use the – the built-in max feature of Python
and again when we’re just doing incremental
changes, we’re going to use the default
dictionary again, we’re going to increment the
value, but instead of keeping track as we go
through, what we’re going to do instead is do
see this max at the end, with a little lambda
function that basically returned the number of
appearances that a given value had in the list
and then returning the maximum key. And to
show you that you can make it even more
compact, you can actually use the set feature of
Python. Pick our initial value, our initial list, turn
it into a set which removes all duplicates and
then use the same max function. And then if
you want to be even more compact, you can
even do it as a one liner, if you wish, and here
what we’re doing is everything in one line, using
the max function, we’re creating a set from our
initial list, so that gives us all the unique values
that we want. And then we’re using the lambda
function to say, give us a count of the number
of times this value appeared in our initial list,
and then return that value. Now, we talked
before – in class, we’ve talked before about
performance. And this is great, this is one-liner
code and that’s fairly understandable, but it’s
actually not nearly as fast as some of the other
things that we’ve done. There is a lot of repeat
passes through the list that occurs because of
the way that we’re doing this. And actually –
probably the fastest one that I’ve seen so far is
this one. Now there are some people on the
forums that may have faster ones and we’ve
been using the comparison functions done by
Anthony Pace to run test on it and this is – it’s
fun to play with. So anyhow, any of these things
work – there’s lots of different ways to find the
mode and a simple and straightforward pass
through a dictionary is a nice way to do it.
And it clearly finishes in time for Theta(n).
4 समस्या में, हम n संख्याओं की एक सूची दी गई है
और हमारे काम मोड में, समय के भीतर खोजने के लिए है
थीटा (n)। और वहाँ के लिए अलग अलग तरीके का एक बहुत कुछ है
और यह क्या-तो, क्या मैंने किया है, मैं चला गया है
माध्यम से और मूल रूप से पाँच अलग अलग तरीके से लिखा
यह कर के। विषय के सभी रूपों वास्तव में। में
पहला मामला है, हम क्या करने जा रहे हैं, हम कर रहे हैं
एक शब्दकोश और जब हम पुनरावृति का उपयोग करने के लिए जा रहा
शब्दकोश का ट्रैक रखते हुए, के माध्यम से
तत्व है कि सबसे अधिक बार देखा गया है। तो,
अगर हम नहीं यहाँ हम सिर्फ शुरू करना, कर रहे हैं
इससे पहले कि हम एक महत्वपूर्ण मूल्य बना हूँ इस मूल्य देखा
जोड़ी और उसके मान 1 पर सेट करें। अगर हम यह देखा है
इससे पहले कि हम सिर्फ वेतन वृद्धि होगी, कुंजी-यह मूल्य
इसके साथ जुड़े मूल्य। के रूप में हम जा रहे हैं,
हम ट्रैक क्या मूल्य-के रख सकते हैं क्या
हम सबसे अधिक देखा है मान। इसलिए, यदि मान कि
हम बस नवीनीकृत किया है पूर्व से अधिक है
अधिकतम मान, हम मौजूदा सेट करेंगे
यह वर्तमान कुंजी मान को अधिकतम मान
जोड़ी। एक परिणाम के रूप में, जब तक हम इस लूप समाप्त,
जो सूची के माध्यम से 1 से गुजारें है, हमें पता चलेगा
मोड या हम में से एक में मान पता चल जाएगा
यदि एक से अधिक मान है मोड,
दिखावे की एक ही नंबर और हम बस हूँ
कि लौटने। वहाँ अलग अलग तरीके का एक बहुत कुछ है आप
यह और कि, उस का एक मामूली परिवर्तन कर सकते हैं
चलो हमें हमारा एक छोटा सा है, जब कोड को छोटा करें आप
अजगर है डिफ़ॉल्ट शब्दकोश का उपयोग कर सकते हैं।
और है कि हम यहाँ क्या कर रहे हैं, हम कह रहे हैं
मूल रूप से पहली बार आप एक कुंजी देखें कि, तुम हो
यह एक प्रारंभिक मान इस पूर्णांक का उपयोग करने देने के लिए जा रहा
समारोह, और यह इसे शून्य का मान देने के लिए जा रहा है।
यह हमें छुटकारा देता है तो क्या कि करने के लिए हमें की अनुमति देता है,
कोड यहाँ का यह छोटा सा, कि देखने के लिए जाँच करें
या नहीं कि क्या मान पहले से ही, जो अस्तित्व
एक हैश तालिका में एक एकल लुक-अप मूल रूप से है। तो,
अब हम क्या हम बस मान बढ़ाना है
द्वारा 1 परवाह किए बिना, और इसलिए पहली बार यह देखता है यह,
यह डिफ़ॉल्ट शब्दकोश मान शून्य का उपयोग करें, जोड़ें करेंगे
यह करने के लिए 1 और हमसे 1, का मान दे तो यह है
मूल रूप से ही हम से पहले क्या किया है के रूप में।
और कोड के बाकी ही है, बस है
अधिकतम मान का ट्रैक रखने और
यह लौटने। तुम एक और बात आप कर सकते है
-में निर्मित अधिकतम सुविधा पायथन का उपयोग कर सकते हैं
और फिर जब हम बस वृद्धिशील कर रहे हैं
परिवर्तन, हम डिफ़ॉल्ट का उपयोग करने के लिए जा रहे हैं
शब्दकोश फिर से, हम जा रहे हैं वेतन वृद्धि करने के लिए
मूल्य, लेकिन रखते हुए बदले ट्रैक के रूप में हम जाने
के माध्यम से, क्या हम बजाय करने के लिए जा रहे हैं क्या है
अंत में, एक छोटी लैम्ब्डा के साथ इस अधिकतम देखें
समारोह है कि मूल रूप से की संख्या में लौटे
रूप से सामने आए कि दिए गए मान सूची में था
और तब अधिकतम कुंजी लौट रहे। और करने के लिए
तुम्हें दिखाने कि तुम इसे और भी कर सकते हैं
कॉम्पैक्ट, आप वास्तव में सेट करें सुविधा का उपयोग कर सकते हैं
अजगर। हमारे प्रारंभिक मूल्य, हमारे प्रारंभिक सूची ले लो, चालू करें
यह एक सेट है जो सभी डुप्लिकेट को हटा में और
तब एक ही अधिकतम फ़ंक्शन का उपयोग करें। और फिर अगर
आप भी और अधिक कॉम्पैक्ट, आप कर सकते हैं किया जा करना चाहते हैं
यहां तक कि यह क्या एक एक लाइनर, यदि आप चाहते हैं, और यहाँ के रूप में
क्या हम कर रहे हैं में से एक में सब कुछ है लाइन है, का उपयोग कर
अधिकतम समारोह में, हम एक सेट से बना रहे हैं हमारे
प्रारंभिक सूची, इसलिए कि हमारे सभी अनन्य मान देता है
हम चाहते हैं कि। और फिर हम लैम्ब्डा का उपयोग कर रहे हैं
कहते हैं, हमें देने के संख्या की गणना करने के लिए समारोह
समय के इस मूल्य हमारे प्रारंभिक सूची में दिखाई दिया,
और फिर उस मान दिया। अब, हम बात की
से पहले-कक्षा में, हम से पहले के बारे में बात है
प्रदर्शन। और यह महान है, यह एक जहाज है
कोड और कि काफी समझा जा सकता है, लेकिन यह है
वास्तव में नहीं लगभग रूप में उपवास के रूप में कुछ अन्य
चीज़ें है कि हम किया है। दोहराने की एक बहुत कुछ है
के कारण होता है जो सूची के माध्यम से गुजरता
तरीका है कि हम यह कर रहे हैं। और वास्तव में-
शायद कि मैं अब तक देखा है सबसे तेजी से एक है
यह एक। अब कुछ लोग वहाँ पर हैं
मंचों कि हो सकता है लोगों को तेजी से और हम है
तुलना कार्य द्वारा किया जाता का उपयोग किया गया
एंथनी गति परीक्षण यह और इस पर चलाने के लिए है-यह है
आनन्द के साथ खेलने के लिए। तो किसी भी तरह, इन बातों का कोई भी
काम-वहाँ अलग अलग तरीके से खोजने के लिए की बहुत सारी है
मोड और एक सरल और सीधा पास
एक शब्दकोश के माध्यम से एक अच्छा तरीका यह करना है।
और यह स्पष्ट रूप से Theta(n) के लिए समय में खत्म।
問4はn個の数のリストからΘ(n)の時間内に 最頻値を求める問題です
やり方はいろいろあります
ここで紹介するのは基本的に5通りの方法です
バリエーションに富んでいます
最初に辞書を使います
辞書を反復させることで
最も頻繁に登場する要素を抜き出します
ここで初期状態に戻します 以前になかった値なら
キー/値を作り値を1とします
以前にあった値ならその値に1を加えます
これを進めていくと最も頻出するものが分かります
値が以前の最頻値より高ければ
現在の最頻値をキー/値に設定し直します
リストを1度ループし終わると
モードか同じ回数登場した値が複数ある場合 モード内の値のうち1つを取り出せます
そしてそれを返します
他にも方法があります
Pythonのデフォルトの辞書を使って コードを少し短くする手法です
これを少し変えて最初にキーを見つけた時に
int機能を用い それを初期値として値をゼロとします
この方法でコードを少し減らすことができ
その値がすでに存在したかどうかチェックできます
ハッシュ表を1度見ればいいだけです
このような場合でも値に1を加えることに変わりはなく
初出の場合はデフォルト辞書で 値を0にし1を加えるので値は1となり
基本的には前回と同じ動きになります
他のコードも同様に 最頻値を見つけたらそれを返します
他にはPythonの組み込み関数maxを 使う方法があります
値に1を加える時にデフォルトを使います
順番に値を検索する代わりに 最後に最頻値を見に行きます
lambda関数でリストの値の頻出度を測り
それをmaxキーに返します
さらにコンパクトにもできます
Pythonのset関数を使う方法です
初期値または初期リストを取り出し 重複を取り除くようにセットします
その後max関数を使います
1行で表す簡潔なコードも作れます
max関数を使って1行にまとめてしまうのです
特定の好きな値を選んで初期リストにセットし
lambda関数を使って
初期リストにこの値が 何度出てきたかをカウントし
その値を返すのです
講義でも説明したやり方です
1行で表されているのでとても分かりやすいのですが
他の方法より処理速度が遅くなってしまいます
この方法はリストの中での繰り返し作業が多いためです
多分一番処理が速いのはこれでしょう
フォーラムでもっと速い方法を考えついた人もいます
アンソニー･ペースさんが考えた比較関数で テストをしてみました
試すのは楽しいです
同じ目的のための様々な異なる方法があります
辞書を使った簡潔な方法を考え出すのは有効です
確実にΘ(n)時間内に終了します