2

実験および学習の目的で。文字列のアルファベット順にバイアスされた値を与えるハッシュ関数から並べ替えアルゴリズムを作成しようとしていたので、理想的にはそのハッシュから適切な場所に配置します。ハッシュバイアスの並べ替え関数を探してみましたが、整数の場合は1つしか見つかりませんでした。目的に合わせて調整すると、メモリを大量に消費することになります。

その理由は、理論的には、このアルゴリズムを正しく実行すれば、O（n）の速度またはほぼそれを達成できるということです。

これが私がこれまでPythonで解決したことです：

letters = {'a':0,'b':1,'c':2,'d':3,'e':4,'f':5,'g':6,'h':7,'i':8,'j':9,
'k':10,'l':11,'m':12,'n':13,'o':14,'p':15,'q':16,'r':17,
's':18,'t':19,'u':20,'v':21,'w':22,'x':23,'y':24,'z':25,
'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,
'K':10,'L':11,'M':12,'N':13,'O':14,'P':15,'Q':16,'R':17,
'S':18,'T':19,'U':20,'V':21,'W':22,'X':23,'Y':24,'Z':25}    

def sortlist(listToSort):
    listLen = len(listToSort)
    newlist = []
    for i in listToSort:
        k = letters[i[0]]
        for j in i[1:]:
            k = (k*26) + letters[j]
        norm = k/pow(26,len(i)) # get a float hash that is normalized(i think thats what     it is called)

        # 2nd part
        idx = int(norm*len(newlist)) # get a general of where it should go
        if newlist: #find the right place from idx
            if norm < newlist[idx][1]:
                while norm < newlist[idx][1] and idx > 0: idx -= 1
                if norm > newlist[idx][1]: idx += 1
            else:
                while norm > newlist[idx][1] and idx < (len(newlist)-1): idx += 1
                if norm > newlist[idx][1]: idx += 1
        newlist.insert(idx,[i,norm])# put it in the right place with the "norm" to ref     later when sorting
    return newlist

前半はいいと思いますが、後半は助けが必要です。したがって、Qは、このようなことを行うための最良の方法であるか、またはこれからO（n）時間（またはその近く）を取得することさえ可能でしょうか？

私が88,000語のリストで行ったテストには、約5分かかり、10,000語には約30秒かかりました。リスト数が増えると、さらに悪化しました。

このアイデアが実際にうまくいく場合は、Cで再コーディングして、実際の速度と最適化を取得します。

2番目の部分は、それが機能するという理由だけであります-たとえ遅くても、私はそれを私の人生のために行うためのより良い方法を考えることができません、私はそれを他のループを行う必要がないものに置き換えたいと思います可能な限り。

あなたが与えることができるアドバイスやアイデアに感謝します。

4

1 に答える 1

3

O（n）でのソートについて：通常、すべての入力、期間に対してソートすることはできません。それは単純に、基本的に、数学的に不可能です。

これが、情報理論に基づく不可能性の素晴らしく短い証明です。並べ替えるには、nを区別できる必要があります。入力の可能な順序。そのためには、log2（n！）ビットのデータを取得する必要があります。これを行うには、O（log（n！））比較を行う必要があります。これはO（n log n）です。O（n）で実行されると主張するソートアルゴリズムは、特殊なデータ（たとえば、固定ビット数のデータ）で実行されているか、正しくありません。

並べ替えアルゴリズムを実装することは良い学習演習ですが、一般的に使用される概念と方法に慣れるまで、既存のアルゴリズムに固執することをお勧めします。そうでなければ、アルゴリズムが機能しない場合はかなりイライラするかもしれません。

楽しく学ぼう！

PS Pythonの組み込みtimsortアルゴリズムは、実際の多くのデータに非常に適しています。したがって、本番コードの一般的な並べ替えアルゴリズムが必要な場合は、通常、.sort/sortedに依存してニーズに十分対応できます。（そして、あなたが理解 timsortできれば、Pythonを使用する人口の90％よりもうまくいくでしょう:)

于 2012-09-27T08:38:41.447 に答える