python：アルゴリズム - 平均からアイテムを集める

Question

これが正しい場所であるかどうかはわかりませんが、アルゴリズムに関連する質問があり、効率的なアルゴリズムはないと思います。 私の問題文を共有することを考えました。:) 私が説明しようとしていることを緩和するために、私は仮説的な例を作りましょう。

と仮定、私は2つのことが含まれているwhcihオブジェクトを含むリストを持っている...

lets say product id and price 

さて、これは在庫のような長い長いlist..sortです..私は持っている。このうちの 低価格、中価格、高価格 の3つの価格区分を定義し、次にk1、k2、k3を計算します。ここで、k1、k2、k3は比率です。 だから、仕事は今、私はこのような方法で、低価格帯のn1製品、中価格帯のn2製品、高価格帯のn3製品があるというような形で製品を集める必要があります... n1：n2 ：n3 == k1：k2：k3

ここで、効率的に以下を達成する方法を説明します。

に、おそらく500ドル とそうであるので、私は100ドルで始まり...そして、その後に見える.. ミッド価格帯を、私は低価格・ポイントが100ドル で目標と私は、この範囲から20個の製品を収集するために持っています90と100の間、100と110の間の項目については、 としましょう。区間1の5つの製品（90,100）と区間1の2つの製品（100,110） 次に、次に低い区間と次の高い区間に行きます。 私はこの間隔で製品の数を得るまでこれを続けます。

どうすればいいですか？また、特定の価格帯の商品数が私の必要以上に少ない場合（おそらく中価格帯は105ドルです...）、その場合はどうすればいいですか。 それが正しいプラットフォームでない場合は私を許してください。質問から、これは「私はこのエラーが発生しました」タイプの質問ではなく、討論的な質問のように見えることがあります。 ありがとう

Answer 1

あなたはおそらくselection algorithmを探しています。
最初にn1の最小要素を見つけて、e1とし、下限リストは、すべてelement <= e1のような要素です。
他の範囲についても同じ処理を行います。下界リストについて

擬似コード：

getLowerRange(list,n): 
    e <- select(list,n) 
    result <- [] 
    for each element in list: 
    if element <= e: 
     result.append(element) 
    return result 

注多くの「同一」の項目がある場合は、この解決策が失敗したことをは、[結果は大きなリストになります]が、これらのアイテムを見つけて、それを削除します結果リストからは難しくありません。

選択アルゴリズムはO(n)であるため、このアルゴリズムはリストのサイズに関連する線形時間を消費することに注意してください。あなたは、単にそれぞれの価格セグメントで3つのリスト、製品のための1つを構築しない理由

Answer 2

リストを使用するのではなく、データベースソリューションを試す必要があるようです。 sqliteをチェックしてください。デフォルトではPythonになっています

Answer 3

アプローチ1

3つの価格のセグメントに属しているものを製品の割り当てが変化しない場合には、（これらのセットは互いに素であると仮定すると）。 これらのリストからランダムに選択することができます（either with or without replacement - 好きなように）。各クラスの項目数は比率によって与えられます。製品価格セグメントの割り当ては関数呼び出しの各セグメントに対応する価格の値を渡すことによって、例えば、事前に指定されることを意図されている場合は

アプローチ2

、あなたはソートされた製品を持っているしたい場合があります価格で検索し、バイナリ検索を使用してm-nearest-neighbors（たとえば）を選択します。比率に応じてパラメータmを指定できます。最大距離を指定すると、希望する価格帯外の商品を拒否することができます。 k = 3価格セグメント、たとえば、にあなたの製品を割り当てる

アプローチ3

品価格セグメントの割り当てが自律的に決定する必要がある場合は、例えば、選択のあなたのclusteringアルゴリズムを適用することができ、k-means、 。実際の製品の選択については、上記と同様に処理を進めることができます。