1

len(list)^2ネストされた 2 つのループを使用して、最速の方法で単一のリストを解析し、比較を回避し、グループ内の重複ファイルを回避する方法についてのアドバイスを探しています。

より正確には、「ファイル」オブジェクトのリストがあり、それぞれにタイムスタンプがあります。ファイルをタイムスタンプと時間オフセットでグループ化したいと考えています。元。ファイル X から始めて、timestamp < (timestamp(x) + offset).

このために、私はしました：

for file_a in list:
   temp_group = group()
   temp_group.add(file_a)
   list.remove(file_a)
   for file_b in list:
      if (file_b.timestamp < (file_a.timestamp + offset)):
         temp_group.add(file_b)
         list.remove(file_b)

   groups.add(temp_group)

（わかりました、コードはもっと複雑ですが、これが主なアイデアです）

ループ中にリストを変更しているため、これは明らかに機能しません。奇妙なことが起こります:)

ループには「リスト」のコピーを使用する必要があると思いましたが、これも機能しません。

for file_a in list[:]:
   temp_group = group()
   temp_group.add(file_a)
   list.remove(file_a)
   for file_b in list[:]:
      if (file_b.timestamp < (file_a.timestamp + offset)):
         temp_group.add(file_b)
         list.remove(file_b)

   groups.add(temp_group)

まあ..リストから要素を削除せずにこれを行うことができることはわかっていますが、すでに「処理済み」のものをマークする必要があり、毎回それらをチェックする必要があります-これは速度のペナルティです.

これを最速/最良の方法で行う方法について誰かアドバイスをもらえますか?

ありがとうございました、

アレックス

編集:質問に正確に答えない別の解決策を見つけましたが、それは私が実際に必要としていたものです(そのように質問するのは私の間違いです)。Python でリストのループに関連する問題を探している人に役立つ可能性があるため、ここに投稿しています。

これは最速ではないかもしれませんが (リストの「パス」の数を考慮すると)、理解して実装するのは非常に簡単で、リストをソートする必要はありません。

並べ替えを避ける理由は、もう少し時間がかかる可能性があることと、グループの最初のセットを作成した後、それらのいくつかが「ロック」され、ロックされていないグループが「解消」され、異なる時間オフセット。(また、グループを解散すると、ファイルの順序が変更される可能性があり、再度並べ替えが必要になります)。

とにかく、解決策はループインデックスを自分で制御することでした。リストからファイルを削除すると、インデックスの増加をスキップします (例: インデックス "3" を削除すると、以前のインデックス "4" は "3" になり、ループ カウンターを増加させたくありません。私はそれをスキップします）。その反復でアイテムを削除しない場合、インデックスは通常どおり増加します。コードは次のとおりです（いくつかの追加機能があります。「バケット」のものはすべて無視してください）：

def regroup(self, time_offset):
    #create list of files to be used for regrouping
    regroup_files_list = []

    if len(self.groups) == 0:
        #on first 'regroup', we start with a copy of jpeg_list, so that we do not change it further on
        regroup_files_list = copy.copy(self.jpeg_list) 

    else:
        i = 0
        while True:
            try:
                group = self.groups[i]
            except IndexError:
                break

            if group.is_locked == False:
                regroup_files_list.extend(group)                    
                self.groups.remove(group)
                continue
            else:
                i += 1

    bucket_group = FilesGroup()
    bucket_group.name = c_bucket_group_name

    while len(regroup_files_list) > 0: #we create groups until there are no files left
        file_a = regroup_files_list[0]
        regroup_files_list.remove(file_a)

        temp_group = FilesGroup()
        temp_group.start_time = file_a._iso_time
        temp_group.add(file_a)

        #manually manage the list index when iterating for file_b, because we're removing files
        i = 0

        while True:
            try:
                file_b = regroup_files_list[i]
            except IndexError:
                break

            timediff = file_a._iso_time - file_b._iso_time              
            if timediff.days < 0 or timediff.seconds < 0:
                timediff = file_b._iso_time - file_a._iso_time

            if timediff < time_offset:
                temp_group.add(file_b)
                regroup_files_list.remove(file_b)
                continue # :D we reuse the old position, because all elements were shifted to the left

            else:
                i += 1 #the index is increased normally

        self.groups.append(temp_group)

        #move files to the bucket group, if the temp group is too small
        if c_bucket_group_enabled == True:                    
            if len(temp_group) < c_bucket_group_min_count:
                for file in temp_group:
                    bucket_group.add(file)
                    temp_group.remove(file)    
            else:
                self.groups.append(temp_group)      

    if len(bucket_group) > 0:
        self.groups.append(bucket_group)
4

3 に答える 3

3

リストをソートし、ジェネレーターを使用してグループを作成することで機能する簡単なソリューション:

def time_offsets(files, offset):

   files = sorted(files, key=lambda x:x.timestamp)

   group = []   
   timestamp = 0

   for f in files:
      if f.timestamp < timestamp + offset:
         group.append(f)
      else:
         yield group
         timestamp = f.timestamp
         group = [timestamp]
   else:
      yield group

# Now you can do this...
for group in time_offsets(files, 86400):
   print group

テストのために実行できる完全なスクリプトを次に示します。

class File:
   def __init__(self, timestamp):
      self.timestamp = timestamp

   def __repr__(self):
      return "File: <%d>" % self.timestamp

def gen_files(num=100):
   import random
   files = []
   for i in range(num):
      timestamp = random.randint(0,1000000)
      files.append(File(timestamp))

   return files
      

def time_offsets(files, offset):

   files = sorted(files, key=lambda x:x.timestamp)

   group = []   
   timestamp = 0

   for f in files:
      if f.timestamp < timestamp + offset:
         group.append(f)
      else:
         yield group
         timestamp = f.timestamp
         group = [timestamp]
   else:
      yield group

# Now you can do this to group files by day (assuming timestamp in seconds)
files = gen_files()
for group in time_offsets(files, 86400):
   print group
于 2009-10-16T18:59:33.687 に答える
1

あなたが何をしようとしているのか正確にはわかりません-リストの順序がグループ化に影響を与えるように思えますが、既存のコードはこのように機能するように変更できます。

#This is O(n^2)
while lst:
    file_a=lst.pop()
    temp_group = group()
    temp_group.add(file_a)
    while lst
        file_b=lst[-1] 
        if (file_b.timestamp < (file_a.timestamp + offset)):
            temp_group.add(lst.pop())
    groups.add(temp_group)

グループはfile_a.timestampから開始する必要がありますか？

# This is O(n)
from collections import defaultdict
groups=defaultdict(list)  # This is why you shouldn't use `list` as a variable name
for item in lst:
    groups[item.timestamp/offset].append(item)

同様のタイムスタンプを持つグループに切り刻むためのはるかに簡単な方法です

于 2009-10-16T20:48:08.207 に答える