Subset eine Liste von dict durch ein Maximum von Duplikaten

Question

Ich habe eine Liste von Diktat mit Bedingungen auf Duplikate Schlüssel unterteilen. Zum Beispiel mit max_duplicates = 2 auf Taste ‚Haupt‘ und die folgenden Liste:

[ 
{'main': 1, 'more': 1}, 
{'main': 1, 'more': 2}, 
{'main': 1, 'more': 3}, 
{'main': 2, 'more': 1}, 
{'main': 2, 'more': 1}, 
{'main': 2, 'more': 3}, 
{'main': 3, 'more': 1} 
] 

Ich mag würde bekommen:

[ 
{'main': 1, 'more': 1}, 
{'main': 1, 'more': 2}, 
{'main': 2, 'more': 1}, 
{'main': 2, 'more': 1}, 
{'main': 3, 'more': 1} 
] 

Die ausgewählten Elemente für einen bestimmten Schlüssel kann zufällig sein, und der Schlüssel Willen sei immer gleich.

Ich bin auf der Suche nach der besten optimierten Lösung. Vorerst dies ist mein Code:

from collections import Counter 
import numpy 


def remove_duplicates(initial_list, max_duplicates): 
    main_counts = Counter([elem["main"] for elem in initial_list]) 
    main_values_for_selection = set([main_value for main_value, count in main_counts.iteritems() 
            if count > max_duplicates]) 
    result = [elem for elem in initial_list 
       if elem["main"] not in main_values_for_selection] 

    for main_value in main_values_for_selection: 
     all_indexes = [index for index, elem in enumerate(initial_list) 
         if elem["main"] == main_value] 
     indexes = numpy.random.choice(a=all_indexes, size=max_duplicates, replace=False) 
     result += [initial_list[i] for i in indexes] 
    return result 

Vielen Dank im Voraus für Ihre Hilfe ;-)

Answer 1

Diese Methode nimmt immer die ersten 2 oder max_duplicate einen bestimmten Schlüssel, den er sieht, aber ich denke, es ist hübsch effizient, die Liste nur auf der Suche durch einmal mit wenigen temporären Variablen:

from collections import defaultdict 

def remove_duplicates(initials,max_dups): 
    dup_tracker = defaultdict(int) 
    rets = [] 
    for entry in initials: 
     if dup_tracker[entry['main']] < max_dups: 
      dup_tracker[entry['main']] += 1 
      rets.append(entry) 
    return rets 

max_dups = 2 
initials = [ 
{'main': 1, 'more': 1}, 
{'main': 1, 'more': 2}, 
{'main': 1, 'more': 3}, 
{'main': 2, 'more': 1}, 
{'main': 2, 'more': 1}, 
{'main': 2, 'more': 3}, 
{'main': 3, 'more': 1} 
] 


rets = remove_duplicates(initials,max_dups)   
print rets 

den Code zu erklären, erstellt defaultdict(int) einen Wörterbuch, in dem jeder Schlüssel (auch wenn es noch nicht definiert ist), mit einem Wert von 0 beginnt. Als nächstes durchlaufen wir die Liste und behalten den Überblick von wievielen von jedem Schlüssel, den wir in der dup_tracker gesehen haben, die ein dict ist, das durch die Werte von 'main' kodiert wird und durch die Zahl geschätzt wird, die sein gesehener spezifischer Schlüssel. Wenn der dup_tracker einige wenige Einträge mit diesem angegebenen Schlüssel gesehen hat, hängt er es an das rets Ausgabearray an und gibt es dann zurück.

TIMED EDIT: Es sieht aus wie die Methode, die ich implementiert habe, ist mindestens ein paar Größenordnungen schneller als deine. Ich habe den ganzen Code, den ich benutzt habe, um sie unten einzutragen.

TL; DR Yours 35.721 seconds vs mine 0.016 seconds, wenn sie auf einer Liste von 50.000 dicts ausgeführt wird, mit Werten von main von 0-10,000

from collections import Counter 
import random 
import time 
​ 
def remove_duplicates_1(initial_list, max_duplicates): 
    main_counts = Counter([elem["main"] for elem in initial_list]) 
    main_values_for_selection = set([main_value for main_value, count in main_counts.iteritems() 
            if count > max_duplicates]) 
    result = [elem for elem in initial_list 
       if elem["main"] not in main_values_for_selection] 
​ 
    for main_value in main_values_for_selection: 
     all_indexes = [index for index, elem in enumerate(initial_list) 
         if elem["main"] == main_value] 
     indexes = numpy.random.choice(a=all_indexes, size=max_duplicates, replace=False) 
     result += [initial_list[i] for i in indexes] 
    return result 
​ 
​ 
def remove_duplicates_2(initials,max_dups): 
    dup_tracker = {} 
    rets = [] 
    for entry in initials: 
     if entry['main'] not in dup_tracker: 
      dup_tracker[entry['main']] = 1 
      rets.append(entry) 
     elif dup_tracker[entry['main']] < max_dups: 
      dup_tracker[entry['main']] += 1 
      rets.append(entry) 
    return rets 
​ 
def generate_test_list(num_total,max_main): 
    test_list = [] 
    for it in range(num_total): 
     main_value = round(random.random()*max_main) 
     test_list.append({'main':main_value, 'more':it}) 
    return test_list 
​ 
max_duplicates = 2 
test_list = generate_test_list(50000,10000) 
​ 
start = time.time() 
rets_1 = remove_duplicates_1(test_list,max_duplicates) 
time_1 = time.time()-start 
​ 
start = time.time() 
rets_2 = remove_duplicates_2(test_list,max_duplicates) 
time_2 = time.time()-start 
​ 
print "Yours",time_1,"vs mine",time_2 

#Results: 
#Yours 35.7210621834 vs mine 0.0159771442413