量子コンピュータによってソートは速くなりますか?

投稿者: Anonymous ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか? 解決 比較ソートに限定した場合、長さ n の配列に対する量子アルゴリズムの時間計算量は Ω(n log n) になる[1]ので、漸近的には古典アルゴリズムの場合と変わりません。 「比較ソート以外の場合はどうなのか?」「他に制限を課した場合はどうなるのか?」についてはよく知りません。英語版 Wikipedia の “Quantum sort” によると空間が制限されたときに量子の方が有利になる場合があるようです。 Høyer, P., Neerbek, J., Shi, Y. (2001). “Quantum complexities of ordered searching, sorting, and element distinctness”. 28th International Colloquium on Automata, Languages, and Programming. pp. 62–73. arXiv:quant-ph/0102078. doi:10.1007/3-540-48224-5_29. 回答者: Anonymous

pythonのsortについて

投稿者: Anonymous あるlistの中の0を全部最後に移動する問題がありました。 たとえば[0,1,0,3,4,5]->[1,3,4,5,0,0] 回答を見たところ、一行で可能でした (numsをinputのlistとすると) nums.sort(cmp=lambda a,b:-1 if b==0 else 0) しかしこのコードの括弧の中がよく理解できません。 どなたか解説していただけないでしょうか?よろしくお願いします。 解決 cmpに指定されているlambda関数は二つのことをやっています。 もし比較先の値が0の時は、比較元の値が何であっても0の方が値が大きいとする(cmpの値が-1) 0でない時は両者を同値とする(cmpの値が0) こうすればリストの中の0は他の値よりも大きな値の扱いになるので、すべて右側に移動することになります。0以外の値はソートされずその場所に留まることになります。下の例なら1,4,3,5はソートされずに元の順序を維持していることがわかります。 >>> nums=[0,1,0,4,3,5] >>> nums.sort(cmp=lambda a,b:-1 if b==0 else 0) >>> print nums [1, 4, 3, 5, 0, 0] 回答者: Anonymous

ActiveRecord4でpolymorphicなScoreの値の合計値でソートしたい。

投稿者: Anonymous TeamモデルとPlayerモデルがhas_manyの関係でpolymorphicなScoreモデルを持つというような構成で チームやプレイヤーに得点を付けることができるシステムを作成しています。 チームに所属しているプレイヤーの一覧を表示するときに Scoreモデルが持つvalueカラムの合計値を使ってソートをかけたいです。 Playerモデルに以下のスコープを作成しました。 scope :sorted, -> { joins(:scores) .group(“players.id”) .order(“sum(scores.value) desc”) } しかし、これだとひとつもスコアを付けられていない要素が含まれずに スコアを付けられている要素の中でソートが行われてしまいます。 スコアが付けられていない要素に対してはデフォルトで0点ということにして 全ての要素を取得したいのですがどうすればよいでしょうか? 解決 似たようなモデル構造のプロジェクトがあったので、実際に動かしながら試してみました。 回答からまず書くと、たぶんこんな感じでいけるんじゃないかと思います。 scope :sorted, -> { joins(“LEFT OUTER JOIN scores ON scores.scorable_id = players.id AND scores.scorable_type = ‘Player'”) .group(“players.id”) .order(“COALESCE(SUM(scores.value), 0) DESC”) } scorable というのはこちらの想像で付けた名前です。ここは実際のカラムの名前に変更してください。 ちなみにクラス定義でいうと、こんな定義をイメージしています。 class Player has_many :scores, as: :scorable class Score…(Continue Reading)

ソートに必要な最低計算量は n log n ではないのか?

投稿者: Anonymous 長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか? 解決 バケットソートやバイトニックソートが逐次の「比較ソート」ではないからです。 比較ソートとは、大雑把に言うと、ランダムアクセスによる読み書きができる配列に対して、操作として要素の比較と読み書きのみが許されている状況下でのソートアルゴリズムのことです。そしてこの比較ソートを逐次に行う場合の平均時間計算量が Ω(n log n) になります。 それ以外の場合、Ω(n log n) を下回ることがあります。バケットソートは配列の要素の種類が分かっていることが前提にあるため、比較ソートではありません。バイトニックソートは並列計算を使ったアルゴリズムであり、逐次のアルゴリズムではありません。 回答者: Anonymous

pandas 日付のソートが上手くいきません

投稿者: Anonymous pandasにてソートを行なったのですが、日付(判明日)の部分だけ、上手くソートされません。日の部分が二桁の際には上手く並び替えられているのですが、どうしても日が一桁の日時が無視してソートされてしまいます。どのようにすれば解決するでしょうか。 df_sort=df3.sort_values([“居住地”,”判明日”]) df_sort.head(50)` 解決 判明日列が 文字列型(str型)なのではないですか? 試しに print(df[‘判明日’].dtype) を実行してみて、object という結果が得られたら文字列です。 文字列のソートの場合、単純に文字列の先頭から比較しますので、例えば ‘2020/3/9’ と ‘2020/3/10’ の比較では、文字列の先頭から’2020/3/’までが同じ値で、次の ‘9’ と ‘1’ の比較となるので ‘2020/3/10′ の方が小さい値と判断されてしまいます。 ということで、この場合は素直’判明日’列をdatetime型に変換した後にソートするべきかと思います。 df3[‘判明日’] = pd.to_datetime(df3[‘判明日’]) sorted_df = df3.sort_values([‘居住地’,’判明日’]) この方法であれば判明日列を日時データの比較でソートを行いますので、求める結果が得られると思います。 回答者: Anonymous

クラスのリストをインスタンス変数に持つクラスのソートがしたい

投稿者: Anonymous class A: def __init__(self, age, name): self.__age=age self.__name=name … def record(self): return {‘age’:age,’name’:name} class Alist: def __init__(self, A): self.__a_list = [A] # あたらしくクラスAを代入する処理が続く のような Python3.5 のコードがあるとして Alistクラスを他のクラスを使って、Aの特定のキーでソートしたい時どのように実装すればよいでしょうか? 解決 こんなんどうでしょうか。 sorted関数で検索対象とするキーを関数で指定できるようです。 それを利用して、Alist に sort_by_age, sort_by_name メソッドを追加してみました。 class A: def __init__(self, age, name): self.__age=age self.__name=name def record(self): return {‘age’:age,’name’:name} # 内部変数をアクセス可能に @property def age(self): return…(Continue Reading)

コマンドプロントのsortの書き換え方法

投稿者: Anonymous Windowsでの作業で困ってます。 DOSコマンドのsortをコマンドプロンプトで使い、ファイルの中身をソートして上書き保存したいのですが、方法が分かりません。 解決 sort input.txt /o output.txt こゆことです? input.txtがsort対象で、output.txtが結果出力が保存されるfileです。 入力と出力を同じfile名にしたら上書きされますよ。 回答者: Anonymous

Pythonでsortした際のエラーについて

投稿者: Anonymous 以下の、test.pyというファイルを実行したところ、エラーが出ます。 sort()の行でエラーが出ているようですが、原因は何でしょうか? また、配列内の要素に虚数が含まれている条件でsortする方法はありますでしょうか? test.py import sys, json sys.path.append(‘/home/vagrant/.local/lib/python3.4/site-packages’) from sympy import * x=Symbol(‘x’) #数値が文字列化された配列 str=[‘-1/4 + sqrt(15)*I/12’, ‘-(135/64 + 15*sqrt(6)/16)**(1/3)/3 – 1/4 + 5/(16*(135/64 + 15*sqrt(6)/16)**(1/3))’] #数値型に変換 list = [sympify(v) for v in str] #並べ替え list.sort() 実行結果 $ python test.py Traceback (most recent call last): File “test.py”, line 12, in <module> list.sort() File…(Continue Reading)

投票結果を投票数が多い順に並べ替えて表示したい

投稿者: Anonymous 以下の関数を実行すると、上から投票数が多い順に (例) 1.13.1.14: 8回 5.11.5.12: 3回 2.13.3.14: 1回 (1.13.1.14の部分が投票内容) といった感じで表示されるはずなんですが、たぶんソートの部分が間違ってて一番大きい投票結果が並び続けてしまいます。 (例) 1.13.1.14: 8回 1.13.1.14: 8回 1.13.1.14: 8回 教えてくれる方いたらよろしくおねがします。 追記 “投票内容”の中身は数値。今回は18になっています。 “投票ボタンが押された回数”の中身は、 (実際) 3.19.8.13 2.19.8.13 3.19.8.13 3.19.8.13 3.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.8.13 2.19.7.13 2.19.7.13 となっています。理想では、show_votes()を実行すると、 (実際) 2.19.8.13:12回 3.19.8.13:4回 2.19.7.13:2回 と画面に表示されます。 function show_votes(){ //数えたい。 $vote_sofar = file(“投票内容”); $times_vote…(Continue Reading)

使用頻度を計算するには?

投稿者: Anonymous 直接プログラミングに関係するわけではありませんが、アルゴリズムの話なのでこちらに質問させていただきます。 いま、アプリ一覧を使用頻度の高い順にソートしたいと考えています。 そこでアプリ起動頻度として、起動と起動のあいだに経過した時間の平均を取るという方法を取っています。 しかしこの方法では、過去によく使用していたが、いまではほとんど使ってないというものが上位に表示されてしまい利便性に問題があります。 そこで皆様のお知恵をお借りしたいのですが、なんらかのものの使用頻度を一般的に求めるためには、どのようなアルゴリズム、計算方法をとるべきでしょうか? よろしくお願いします。 補足 回答いただきありがとうございます。 私が期待しているのは、使用頻度なので、 よく利用する(利用する間隔が短い)ものを上位に 昔良く利用していたが今はもう利用していないものは相対的に下位に 利用回数が多いものを上位に という特徴をもった数値を計算したいと思っています。 解決 時系列データに対して、過去n日の動きを知りたい時は移動平均がよく使われます。直近の値を重視し、遠い過去の影響を少なく計算するには、経過日数の逆数で重み付けすればいいわけです。重み付けのやり方は色々ありますが指数移動平均もよく使われています。 例えば1日あたりの起動回数をアプリごとにカウントし、窓の大きさを1ヶ月などとすれば過去1ヶ月の動きが分かります。リリース日からということなら1年とか、長期間になるでしょう。 回答者: Anonymous