Блог

Главная - Вопросы по программированию - Ищете самый быстрый способ разделить ключи словаря (на основе значений) на списки списков таким образом, чтобы каждый список не пересекал определенный порог

Ищете самый быстрый способ разделить ключи словаря (на основе значений) на списки списков таким образом, чтобы каждый список не пересекал определенный порог

#python #algorithm #dictionary #data-structures #sliding-window

Вопрос:

У меня есть заказанный каталог a = {"1":800, "2":400, "3":600, "4":200, "5":100, "6":400}

Я хотел бы разделить ключи на список списков таким образом, чтобы общие значения каждого списка не превышали порогового значения (в данном случае 600), или если значение превышает пороговое значение, у него должен быть свой собственный список. Кроме того, мы проверяем только наличие следующей клавиши (например, в скользящем окне).

Приведенный выше словарь должен вернуться expected = [['1'], ['2'], ['3'], ['4', '5'], ['6']] . Например, '1' имеет свой собственный список, так как он превышает пороговое значение. '2' имеет свой собственный список, так как значения '2' '3' превышают пороговое значение. ['4', '5'] имеет суммарные значения до 600 , и если мы добавим '6' , это превысит пороговое значение.

Вот что у меня есть до сих пор:

 def check_result(a):
    
    result = {}
    curr_val = 0 
    threshold = 600
    l =[]
    result = []

    for i in a.keys():
        if curr_val >= threshold:
           result.append(l)
           l = []
           curr_val = 0

        if curr_val   a[i] > threshold:
          result.append(l)
          l = [i]
          curr_val = a[i]
        else:
          l.append(i)
          curr_val  = a[i]

    

   result.append(l)
   print(result)

Он выдает результат как [[], ['1'], ['2'], ['3'], ['4', '5'], ['6']] .

Ищу правильное решение за O(n) времени.

Спасибо!

Комментарии:

1. обновил его, он должен был быть l

2. Почему вы думаете, что ваше решение не является O(n)?

3. Подсписок должен быть непрерывным?

4. Да @DaniMesejo

5. @mkrieger мое решение прямо сейчас находится в O(n), но я не думаю, что оно на 100% правильное, также мне интересно, есть ли более чистый способ

Ответ №1:

У второго if просто должна быть дополнительная проверка, которая l не пуста:

 if curr_val   a[i] > threshold and l:

Ответ №2:

Немного менее громоздкий код:-

 a = {"1": 800, "2": 400, "3": 600, "4": 200, "5": 100, "6": 400}


def check_result(d):
    T = 600
    result, e = [], []
    s = 0
    for k, v in d.items():
        if e:
            if s   v > T:
                result.append(e)
            else:
                e.append(k)
                s  = v
                continue
        e = [k]
        s = v
    if e:
        result.append(e)
    return result


print(check_result(a))

Ответ №3:

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

 a =  {"1":800, "2":400, "3":600, "4":200, "5":100, "6":400}
t = 600  # Treshold

r = []   # result, list of lists of keys
s = 0    # running sum
for k,v in a.items():
    group,item,delta = (r[-1],k,v) if r and s v<=t else (r,[k],v-s)
    group.append(item)  # append to result or last sublist
    s  = delta          # update running sum

print(r)
[['1'], ['2'], ['3'], ['4', '5'], ['6']]

Или этот несколько более короткий (но менее эффективный) вариант:

 r,s = [],0   # result, running sum
for k,v in a.items():
    r  = [r.pop(-1) [k] if r and s v<=t else [k]]
    s  = v - s*(s v>t)
Метки: ,