Пометка повторяющихся записей в массиве numpy как True

От: Из: Общие

Итак, проблема в том

Найдите повторяющиеся записи (2-е вхождение и далее) в заданном массиве numpy и пометьте их как True. Первое появление должно быть ложным.

И мое решение:

import numpy as np


def duplicates(a):
    uniques = np.unique(a)
    result = []
    for i in a:
        if i not in uniques:
            result.append(True)
        else:
            result.append(False)
            uniques = np.delete(uniques, np.where(uniques == i))
    return result


np.random.seed(100)
a = np.random.randint(0, 5, 10)
print('Array: ', a)
print(duplicates(a))

Какие улучшения я могу сделать в этой программе?

3 ответа
3

Я бы сказал, что ваш код — хороший код. В этом нет ничего плохого. Единственное, что вы можете написать более или менее один и тот же алгоритм намного короче, и это, по сути, означает, что вам нужно реорганизовать весь свой код до одной строки.

Итак, прежде чем взглянуть на упрощенную версию того, что вы написали, позвольте мне просто указать, что имена переменных должны быть описательными, и если вы используете сокращения или однобуквенные имена, вам следует придерживаться наиболее использованные условные обозначения. Почему я это говорю? Хорошо, i обычно называют неважным индекс переменная, но в вашем цикле у вас есть for i in a, а также i является элементом массива … Так что, хотите верьте, хотите нет, люди, просматривающие остальную часть вашего кода, могут быть сбиты с толку тем фактом, что i не является индексом.

Промежуточный шаг

Итак, прежде чем переходить к однострочному, на самом деле удобочитаемый (т.е. это хороший код Python) давайте посмотрим на более понятный промежуточный шаг. Вместо того, чтобы вычислять все уникальные значения и затем удалять оттуда (удаление из середины списка обычно «медленное»), вы можете пойти другим путем и получить список, в котором сохраняются все найденные вами уникальные значения:

def duplicates(arr):
    result, uniques = [], []
    for elem in arr:
        if elem in uniques:
            result.append(True)
        else:
            result.append(False)
            uniques.append(elem)
    
    return result

Следующий промежуточный шаг

А теперь еще раз взгляните на то, что я написал. Обратите внимание, что оба в if и else Я добавляю к result Переменная. Единственное, что действительно «особено», — это добавление к uniques, что происходит только на else, чтобы мы могли написать .append безоговорочно и добавить к uniques только при необходимости:

def duplicates(arr):
    result, uniques = [], []
    for elem in arr:
        result.append(elem in uniques)
        if elem in not uniques:
            uniques.append(elem)
    
    return result

Окончательное решение (после переосмысления алгоритма)

Дайте мне знать, если вы понимаете предложенное мной решение, и я расширю его, если вам нужно 🙂

def duplicates(arr):
    return [elem in arr[:i] for i, elem in enumerate(arr)]

Обратите внимание, что это понимание списка читается как «вернуть список, в котором указано, может ли i-й элемент быть найден в первых элементах i-1».

Главное здесь — правильно сформулировать результат. Если вы правильно рассмотрите код Python, английский язык и код станут одним и тем же.

Когда у вас относительно простой for цикл, который строит список с последовательными .append, это знак, чтобы попробовать и посмотреть, сможете ли вы использовать понимание списка.

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

РЕДАКТИРОВАТЬ:

Как отмечали другие ответы (а также см. Комментарии к этому ответу), этот однострочный алгоритм работает с временной сложностью O (n ^ 2), что не лучшее, что вы можете сделать. Тем не менее, эта единственная строка Python показывает вам, как далеко вы можете зайти с простой идеей / наивным алгоритмом и оптимизированным использованием основных функций Python 🙂

  • 1

    В этом случае это должно быть False, True, True. Значение False присваивается только при первом появлении значения в массиве. Спасибо за ваши объяснения и советы, я очень ценю участие в этом сообществе 🙂

    — Левон Аветисян

  • @LevonAvetisyan ага, я более спокойно посмотрел на ваш код и, конечно же, это понял!

    — РГО

  • 2

    Лучше сделай uniques а set.

    — Мануэль

  • @Manuel лучшая производительность при проверке наличия элемента? (Разве спектакль не будет Добавлять новый элемент будет хуже?) Или почему вы это предлагаете?

    — РГО


  • 2

    Да, все это делается за O (n) вместо O (n ^ 2). Кроме того, тогда вы можете снять дополнительную проверку.

    — Мануэль

Как упоминалось в комментариях к другому ответу, вы должны использовать sets для проверки членства, когда это возможно. Совместите это с наращиванием uniques вместо того, чтобы урезать его, мы получаем очень простую реализацию:

def duplicates(numbers):
    uniques = set()
    result = []

    for num in numbers:
        result.append(num in uniques)
        uniques.add(num)

    return result

Эта реализация duplicates краток, легко читается и запускается в O (n) вместо O (n ^ 2), что является основным отличием. Однострочники — это забавное упражнение, которое может научить вас некоторым интересным аспектам Python, и я понимаю их привлекательность, но часто это не лучший вариант. Не стоит жертвовать удобочитаемостью и производительностью ради написания меньшего количества строк кода.

РЕДАКТИРОВАТЬ: тестирование производительности

Как и просили в комментариях, я протестировал производительность трех разных подходов:

def duplicates_set(numbers):
    uniques = set()
    result = []

    for num in numbers:
        result.append(num in uniques)
        uniques.add(num)

    return result


def duplicates_list(numbers):
    result, uniques = [], []
    for elem in numbers:
        if elem in uniques:
            result.append(True)
        else:
            result.append(False)
            uniques.append(elem)

    return result


def duplicates_oneliner(numbers):
    return [elem in numbers[:i] for i, elem in enumerate(numbers)]

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

def duplicates_list(numbers):
    result, uniques = [], []
    for elem in numbers:
        result.append(elem in uniques)
        if elem not in uniques:
            uniques.append(elem)

    return result

Вот мой код для тестирования производительности с использованием timeit модуль. Все предоставленные выходные данные были произведены этим кодом.

num_range: (int, int)
random_nums: int
executions: int

np.random.seed(100)
a = np.random.randint(*num_range, random_nums)

from timeit import timeit

print(f"{executions} executions with {random_nums} random numbers in range {num_range}")
print("duplicates_set:", "t" * 2, timeit(stmt=lambda: duplicates_set(a), number=executions))
print("duplicates_list:", "t" * 2, timeit(stmt=lambda: duplicates_list(a), number=executions))
print("duplicates_oneliner:t", timeit(stmt=lambda: duplicates_oneliner(a), number=executions))

Начиная с 100_000 выполнений с параметрами из исходного вопроса, мы получаем следующий результат:

100000 executions with 10 random numbers in range (0, 5)
duplicates_set:          0.22261620000000001
duplicates_list:         0.18974730000000006
duplicates_oneliner:     2.9783912

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

Увеличивая длину массива случайных чисел до 1_000, мы получаем такой результат:

1000 executions with 1000 random numbers in range (0, 5)
duplicates_set:          0.1603748
duplicates_list:         0.13001250000000003
duplicates_oneliner:     3.1837349

Кажется, что длина массива сама по себе не влияет на относительную производительность duplicates_set а также duplicates_list. Пока диапазон чисел невелик, list выходит на первое место. Относительная производительность оставалась неизменной до 1_000_000 элементов, что имеет смысл, поскольку размер uniques ограничен диапазоном чисел.

Как только мы начнем увеличивать num_range, то set реализация действительно начинает сиять, так как она просто не заботится о размере uniques когда дело доходит до времени выполнения:

1000 executions with 1000 random numbers in range (0, 10)
duplicates_set:          0.15972010000000003
duplicates_list:         0.15932980000000002
duplicates_oneliner:     3.1950098

Для ряда (0, 10), set а также list реализация примерно такая же.

В диапазоне (0, 1_000) в list реализация уже превосходит однострочный:

1000 executions with 1000 random numbers in range (0, 1000)
duplicates_set:          0.15644170000000002
duplicates_list:         3.4406095
duplicates_oneliner:     3.1854200999999995

Однако однострочник сразу выходит из конкурса, как только ввод становится больше, даже при небольших диапазонах чисел:

10 executions with 100000 random numbers in range (0, 10)
duplicates_set:          0.1576303
duplicates_list:         0.24761889999999998
duplicates_oneliner:     30.1282213

Конечный результат именно такой, как и следовало ожидать:

  • duplicates_list действительно начинает бороться, когда количество уникальных чисел увеличивается, поскольку if elem in uniques становится все дороже.
  • duplicates_oneliner полностью не работает с длинными списками ввода, так как elem in numbers[:i] становится очень быстро.
  • duplicates_set уступает только при небольшом количестве уникальных чисел, но в масштабе он превосходит обе другие реализации с огромным отрывом, поскольку if elem in uniques можно проверить в постоянное время.

  • Я согласен с тем, что ваше решение краткое и разборчивое, и мне нравится ваше безоговорочное uniques.add, отлично сработано! +1 от меня 🙂

    — РГО

  • Однако вы, похоже, намекаете, что мое решение не читается и не работает. Хотя это факт, что его сложность составляет O (n ^ 2) и, следовательно, менее производительна, я думаю, мы можем согласиться с тем, что одна строка по-прежнему очень разборчива и хорошо демонстрирует, как далеко вы можете зайти с довольно наивным алгоритмом. Наконец, мне интересно, если решение, использующее set действительно O (n), если в массиве слишком много уникальных элементов. Я бы ожидал либо set использовать путь к большой памяти быть O (1) при вставке и проверке членства или быть чем-то вроде O (log n) для проверки членства, нет? У вас есть ссылки для меня, чтобы узнать? 🙂

    — РГО

  • 1

    @RGS В этом ты прав sets используют больше памяти, чем списки, поскольку значения хеш-значений должны храниться в дополнение к самим элементам. Сравнение памяти на SO. Однако ваше предположение о том, что проверка членства не является O (1), неверно. setпесок dicts) реализованы с использованием хэш-таблиц, обеспечивающих поиск и вставки O (1). Глава 4 в Высокопроизводительный Python: Словари и наборы

    — рискованный пингвин

  • 2

    @RGS Это безусловное add Кстати, это то, что я имел в виду, говоря «Плюс, тогда вы можете снять лишнюю проверку». После этого я подозреваю, что однострочный и набор-решение примерно одинаково читаемы в целом, а однострочный более читабельный для людей, привыкших к ним 🙂

    — Мануэль


  • 1

    Ну что ж, теперь к моему ответу добавлены тесты (те же случаи, что и у вас).

    — Мануэль

Проверить uniqueс документация опять же, он предлагает дать вам индексы:

def duplicates(a):
    uniques = np.unique(a, True)[1]
    result = a == a
    result[uniques] = False
    return result

В тестах (повторное использование рискованного пингвина) он средний для крошечного оригинального случая, но, безусловно, самый быстрый для всех более крупных случаев:

100000 executions with 10 random numbers in range (0, 5)
duplicates_original  17.807 17.395 18.284 seconds
duplicates_set        0.726  0.686  0.721 seconds
duplicates_list       0.631  0.548  0.587 seconds
duplicates_oneliner   7.087  6.946  7.822 seconds
duplicates_numpy      2.017  2.177  2.155 seconds

1000 executions with 1000 random numbers in range (0, 5)
duplicates_original   6.904  6.862  6.617 seconds
duplicates_set        0.520  0.535  0.584 seconds
duplicates_list       0.385  0.363  0.341 seconds
duplicates_oneliner   7.241  7.927  7.244 seconds
duplicates_numpy      0.062  0.065  0.063 seconds

1000 executions with 1000 random numbers in range (0, 10)
duplicates_original   6.720  6.885  6.801 seconds
duplicates_set        0.656  0.542  0.576 seconds
duplicates_list       0.459  0.511  0.509 seconds
duplicates_oneliner   7.556  7.064  7.637 seconds
duplicates_numpy      0.080  0.082  0.073 seconds

1000 executions with 1000 random numbers in range (0, 1000)
duplicates_original  25.222 26.108 24.767 seconds
duplicates_set        0.682  0.757  0.759 seconds
duplicates_list      11.608 11.651 11.196 seconds
duplicates_oneliner   8.320  7.949  7.608 seconds
duplicates_numpy      0.101  0.110  0.102 seconds

10 executions with 100000 random numbers in range (0, 10)
duplicates_original   6.577  6.658  6.637 seconds
duplicates_set        0.609  0.585  0.603 seconds
duplicates_list       0.514  0.524  0.508 seconds
duplicates_oneliner  36.337 36.677 35.764 seconds
duplicates_numpy      0.082  0.083  0.083 seconds

Код эталонного теста:

from timeit import timeit
import numpy as np

def duplicates_original(a):
    uniques = np.unique(a)
    result = []
    for i in a:
        if i not in uniques:
            result.append(True)
        else:
            result.append(False)
            uniques = np.delete(uniques, np.where(uniques == i))
    return result

def duplicates_set(numbers):
    uniques = set()
    result = []

    for num in numbers:
        result.append(num in uniques)
        uniques.add(num)

    return result

def duplicates_list(numbers):
    result, uniques = [], []
    for elem in numbers:
        if elem in uniques:
            result.append(True)
        else:
            result.append(False)
            uniques.append(elem)

    return result

def duplicates_oneliner(numbers):
    return [elem in numbers[:i] for i, elem in enumerate(numbers)]

def duplicates_numpy(a):
    uniques = np.unique(a, True)[1]
    result = a == a
    result[uniques] = False
    return result

def benchmark(num_range: (int, int), random_nums: int, executions: int):

    np.random.seed(100)
    a = np.random.randint(*num_range, random_nums)

    print(f"{executions} executions with {random_nums} random numbers in range {num_range}")

    solutions = [
        duplicates_original,
        duplicates_set,
        duplicates_list,
        duplicates_oneliner,
        duplicates_numpy,
    ]

    # Correctness
    expect = list(solutions[0](a))
    for solution in solutions:
        assert list(solution(a)) == expect

    # Speed
    for solution in solutions:
        ts = ['%6.3f' % timeit(stmt=lambda: solution(a), number=executions)
              for _ in range(3)]
        print(solution.__name__.ljust(20), *ts, 'seconds')
    print()

benchmark((0, 5), 10, 100000)
benchmark((0, 5), 1000, 1000)
benchmark((0, 10), 1000, 1000)
benchmark((0, 1000), 1000, 1000)
benchmark((0, 10), 100000, 10)

Это тоже хорошее решение! Важно знать функции вашей библиотеки 🙂 +1

— РГО

Похожие записи:

  1. C99 JSON парсер / писатель
  2. Создание вопросов и ответов на умножение для приложения в стиле викторины
  3. Будильник подкласс часов
  4. Реализация простого общего указателя C ++
  5. Тротлинг видеокарты asus zephirus s17 gx701lxs

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *