Более быстрый способ перебора большого списка в Python

Question

Я написал некоторый код, включенный ниже, чтобы помочь мне найти почти повторяющиеся изображения в папке с приблизительно 65К изображениями. Прямо сейчас я делаю это в три этапа:

1. Рассчитать среднее значение-га sh для каждого изображения в каталоге и сохранить в словарь
2. Перебирать элементы каталога и вычислить разницу между хешами. Я также вычисляю среднеквадратичную разницу между гистограммой изображений в определенных промежуточных случаях, когда разница ha sh велика (для выявления некоторых дополнительных случаев)
3. Удаление изображений

Шаг 1 занимает около 3 минут в большой папке, однако шаг 2 занимает вечность. Запуск в течение +5 часов без результата. Я думаю, что есть лучший способ сделать это, но я не знаю много об улучшении скорости вычислений.

Какой хороший способ улучшить скорость?

import imagehash 
import PIL 
from pathlib import Path
import os
import time
import pandas as pd
import math

def timer(start,end):
    hours, rem = divmod(end-start, 3600)
    minutes, seconds = divmod(rem, 60)
    return("{:0>2}:{:0>2}:{:02.0f}".format(int(hours),int(minutes),seconds))

#step 1 make hashes 
def get_hash_dict(mypath, hash_size = 16 ):
    start = time.time()
    d = {} 
    file_list = os.listdir(mypath)
    for i in file_list: 
        try: 
            im = PIL.Image.open(os.path.join(mypath, i)) 
        except: 
            continue 
        d[i] = imagehash.average_hash(im, hash_size=hash_size)  

    print(len(d),len(file_list)) 
    print("Elapsed time {}".format(timer(start,time.time())))
    return(d)

# remove all with a small cutoff 
# double-check those with larger cutoff
#step 2
def get_dups(file_list,d, hash_size=16):
    start = time.time()
    cutoff_small = int(.06*hash_size**2) #6% difference is identical
    cutoff_large = int(.15*hash_size**2) # 16% has many false positives
    cutoff_rms = 580 
    res = []
    double_check = []
    dont_check = set()
    to_delete=[]
    freqs=[]
    another_check=[]

    for i, f1 in enumerate(file_list[:-2]):
        hash0 = d[f1] 
        temp1 = [f1]
        temp2 = [f1]
        temp3 = [f1]
        for f2 in file_list[i+1:]:
            if f2 not in dont_check:
                dubbles = []
                hash1 = d[f2]
                temp = hash0-hash1

                if temp < cutoff_small:
                    temp1.append([f2,temp]) 
                    temp2.append(f2)
                    dont_check.add(f2)
                    freqs.append(temp)
                # double check if the error is too high
                elif temp < cutoff_large:
                    freqs.append(temp)
                    i1 = PIL.Image.open(os.path.join(mypath, f1)).histogram()
                    i2 = PIL.Image.open(os.path.join(mypath, f2)).histogram()
                    rms = math.sqrt(sum([(a-b)**2 for (a,b) in zip(i1, i2)])/len(i1))
                    if rms < cutoff_rms:
                        temp3.append(f2)
                        another_check.append([f1,f2])

        if len(temp1)>=2:
            res.append(temp1)
            to_delete.append(temp2)
        if len(temp3)>=2:
            double_check.extend(temp3)

    double_check_2 = list(set(double_check) - dont_check)
    res_doubles = []
    dont_check = set()
    for i,f1 in enumerate(double_check_2):
        if f1 not in dont_check:
            temp = [f1]
            for j,f2 in enumerate(double_check_2[i+1:]):
                i1 = PIL.Image.open(os.path.join(mypath, f1)).histogram()
                i2 = PIL.Image.open(os.path.join(mypath, f2)).histogram()
                rms = math.sqrt(sum([(a-b)**2 for (a,b) in zip(i1, i2)])/len(i1))
                if rms < cutoff_rms and d[f1]-d[f2]<=cutoff_large:
                    temp.append(f2)
                    dont_check.add(f2)
            res_doubles.append(temp)

    print("Elapsed time {}".format(timer(start,time.time())))
    plt.hist(freqs, color='g')
    plt.show() 
    return(to_delete,res_doubles,another_check)

#find biggest file, remove others
def keep_largest(all_files):
    count=0
    to_keep=[]
    to_remove=[]
    for i in all_files:
        s_max = 0
        for j in i:
            temp = os.stat(os.path.join(mypath, j)).st_size
            if temp > s_max:
                keep_temp = j
                s_max = temp
        to_keep.append(keep_temp)

    to_keep = set(to_keep)
    print('Keeping ',len(to_keep))
    for i in all_files:
        for j in i:
            if j not in to_keep:
                try:
                    #os.remove(os.path.join(mypath,i))
                    count+=1
                except:
                    continue

    print("Deleted {} files".format(count))

Answer 1

Вместо того, чтобы пересчитывать гистограмму для каждого изображения каждый раз, создайте функцию getHistogram, которая кэширует гистограмму, а не восстанавливает ее для одного и того же файла несколько раз.