Оптимизация дедупликации

Проблема заключается в следующем. Мне нужна функция, которая, учитывая список и максимальное количество вхождений «x», удаляет все элементы списка, которые появляются более x раз или x раз.

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

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

Мой код следует.

typedef struct n_s
{
    int val;
    struct n_s *next;
}
n_t;

// deletes all elements equal to del in list with head h
n_t * delete(n_t *h, int del);
// returns the first occurrence of find in list with head h, otherwise gives NULL
n_t * find(n_t *h, int find);

n_t *
delFromList(n_t *h, int x)
{
    int val;
    n_t *el, *posInter;

    // empty list case
    if (h == NULL)
        return NULL;

    // first element
    val=h->val;
    if ( (posInter = find(h -> next,val)) 
        && (find(posInter -> next, val)))
        h = delete(h, val);

    // loop from second element
    el = h;
    while (el -> next)
    {
        val = el -> next -> val;
        // check whether you want to delete the next one, 
        // and then if you do so, check again on the "new" next one
        if ((posInter = find(el -> next -> next, val))                   
            && (find(posInter -> next, val)))
            el -> next = delete(el -> next, val);
        // in case you did not delete the nexy node, you can move on
        else 
            el = el -> next;

    }

    return h;
}

Я знаю, что el->next->next может показаться запутанным, но я считаю менее интуитивным использование таких переменных, как «следующий», «прошлый»… так что извините за головную боль.

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

Eric Postpischil 08.01.2023 16:00

«у вас мало очень больших чисел, и ваша память этого не сделает»: что?

Yves Daoust 08.01.2023 16:01

Можно ли изменить определение списка? Если да, у вас может быть третье поле, которое отслеживает время, когда значение «появляется» в списке. Это означало бы, что вам придется полностью изменить всю вашу программу.

Magic Thanos 08.01.2023 16:01

Не лучшая идея объявлять массив из 100000 номеров, когда в вашем списке есть 0, 1, 2 и 99999 @YvesDaoust. Наверное, я должен был использовать пример

Simone Licciardi 08.01.2023 16:02

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

Eric Postpischil 08.01.2023 16:02

@YvesDaoust: диапазон значений данных настолько велик, что им не хватает памяти для массива, индексированного по значению данных.

Eric Postpischil 08.01.2023 16:03

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

Yves Daoust 08.01.2023 16:03

Это задание класса @EricPostpischil, но у меня нет особых ограничений, кроме использования экзотических библиотек. Мне просто было интересно, могу ли я упростить или улучшить вычислительное решение.

Simone Licciardi 08.01.2023 16:03

Что за задание? Чтобы выполнить задание по дедупликации или оптимизировать время вычислений задания по дедупликации?

Eric Postpischil 08.01.2023 16:04

@YvesDaous, почему лучше использовать curr и succ? Я не очень понимаю практику. вам нужно управлять большим количеством переменных... для меня это только делает код более запутанным и подверженным ошибкам

Simone Licciardi 08.01.2023 16:05

Работа состоит в том, чтобы сделать это. Но из любопытства я тоже пытался его оптимизировать... Я пишу код не для класса, а для улучшения своих навыков.

Simone Licciardi 08.01.2023 16:06

Ну, насколько я вижу, у него нет проблем с управлением целыми числами @YvesDaoust.

Simone Licciardi 08.01.2023 16:07
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
0
12
92
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Ответ принят как подходящий

Один из вариантов алгоритма с улучшенной производительностью:

  • Определите структуру данных D с двумя элементами, один для значения элемента списка и один для подсчета количества его появления.
  • Инициализировать пустое сбалансированное дерево, упорядоченное по значению.
  • Итерация по списку. Для каждого элемента в списке найдите его в дереве. Если его нет, вставьте в это дерево структуру D, скопировав элемент значения из элемента списка и установив его счетчик равным единице. Если он присутствует в дереве, увеличивает его счетчик. Если его количество равно порогу или превышает его, удалите его из списка.

Поиски и вставки в сбалансированном дереве выполняются за O(log n). Связанный список из n элементов использует n из них, а удаление из связанного списка — O(1). Таким образом, общее время равно O(n log n).

Используйте карту подсчета, чтобы подсчитать, сколько раз появляется каждый элемент. Ключи — это элементы, а значения — счетчики.

Затем просмотрите свой массив во второй раз, удалив все, что соответствует вашему порогу.

O(n) времени, O(n) дополнительного пространства.

Для карты требуется либо более O(n) времени (более O(1) на элемент для n элементов), либо O(r) пространства, где r — это диапазон элементов, а не их количество.

Eric Postpischil 08.01.2023 16:38

@EricPostpischil Это относится к возможности того, что хэш-функция производит большое количество коллизий относительно количества различных входных данных?

Dave 08.01.2023 16:45

@EricPostpischil В любом случае, я не понимаю, почему диапазон элементов имеет значение. Карта, которая имеет два очень далеких друг от друга элемента, не обязательно должна быть массивной.

Dave 08.01.2023 17:35

Если у вас нет памяти O(r) для карты, могут быть коллизии, и вам нужно как-то управлять ими, а это невозможно сделать за время O(1) на коллизию.

Eric Postpischil 09.01.2023 01:23

@EricPostpischil Я должен придерживаться своего ответа. На вероятность коллизий влияет количество хэшируемых уникальных элементов и пространство, используемое картой, но не диапазон хешируемых элементов. Например, скажем, у нас есть два набора вещей для хеширования. Набор «A» имеет {1, 10 ^ 100}, а набор «B» содержит все целые числа от 1 до 100. Для карты одинакового размера у B гораздо больше шансов столкнуться с коллизиями, чем у A.

Dave 09.01.2023 05:47

Вы можете заявить, что ваш алгоритм имеет хорошую производительность в некоторых подмножествах случаев. Но обозначение «О» означает, что ограничение применяется ко всем случаям. Утверждение, что алгоритм использует время O(n) с пространством O(n), неверно.

Eric Postpischil 09.01.2023 12:23

@EricPostpischil В Википедии указано O(n) пробел: en.wikipedia.org/wiki/Hash_table, CLRS Intro to Algorithms говорит O(n) пробел (2-е изд., глава 11.2 «Хеш-таблицы»).

Dave 09.01.2023 13:57

Да, хеш - это пространство O (n). Это не время O (n), как неправильно говорит этот ответ. Как говорится в моем комментарии, карта либо требует больше, чем O (n) времени, либо требует O (r) места. Заявление о том, что решение карты равно O (n) времени и O (n) пространству, неверно.

Eric Postpischil 09.01.2023 14:21

@EricPostpischil Вы были бы удовлетворены, если бы я добавил слово «ожидаемый» - ожидаемое время O (n), поскольку все хеш-операции ожидаются за время O (1)? Я до сих пор не знаю, откуда вы получаете O(r) — диапазон не имеет значения.

Dave 09.01.2023 15:18

Другие вопросы по теме