Может ли тестировании реализаций односвязного списка быть в 100 раз быстрее множества?

@Дилендик · Регистрация: 20.07.2011

Студворк — интернет-сервис помощи студентам

У меня несколько вопросов.
1. Может ли при тестировании реализаций односвязного списка и множества при синхронизации потоков, список проходить тестирование в 100 раз быстрее? Почему?
2. Может ли при ленивой синхронизации односвязного списка операция проверка проходить быстрее в два раза чем операция удаление? Почему?

@Дилендик · 11.01.2021, 19:52 **[ТС]**

Потоки

@oleg-m1973 · 11.01.2021, 19:57

Сообщение от Дилендик

Потоки

Что потоки?

Добавлено через 3 минуты
LazySyncList ни разу не многопоточный. Т.е. обращаться к нему нужно либо из одного потока, либо синхронизировать обращения к нему, что то же самое, что один поток.

@Дилендик · 11.01.2021, 20:05 **[ТС]**

Сообщение от oleg-m1973

Сообщение от Дилендик
Может ли тестировании реализаций односвязного списка быть в 100 раз быстрее множества?
Кстати это этот LazySyncList работает в сто раз быстрее "множества"? Или он и есть то самое множество?

Чужой код вывесить не могу. Поэтому первый вопрос снимаю. Остаётся только второй.
2. Может ли при ленивой синхронизации односвязного списка операция проверки проходить быстрее в два раза чем операция добавления? Почему? См. файл 1 https://yadi.sk/i/aWk1V7pedJxTyQ

Добавлено через 4 минуты

Сообщение от oleg-m1973

Что потоки?
Добавлено через 3 минуты
LazySyncList ни разу не многопоточный. Т.е. обращаться к нему нужно либо из одного потока, либо синхронизировать обращения к нему, что то же самое, что один поток.

И что делать? Мне то нужно ленивую синхронизацию применить. И многопоточность должна быть.
Что исправлять? Где смотреть?

@oleg-m1973 · 11.01.2021, 20:08

Сообщение от Дилендик

Чужой код вывесить не могу. Поэтому первый вопрос снимаю. Остаётся только второй.
2. Может ли при ленивой синхронизации односвязного списка операция проверка проходить быстрее в два раза чем операция добавления? Почему? См. файл 1

Если ты о том коде, который показал, то он кривой. Методы LazySyncList нельзя вызывать одновременно в разных потоках, нужно синхронизировать

Добавлено через 1 минуту

Сообщение от Дилендик

И что делать? Мне то нужно ленивую синхронизацию применить. И многопоточность должна быть.
Что исправлять? Где смотреть?

Что такое "ленивая синхронизация"? Я только обычную знаю.

@Дилендик · 11.01.2021, 20:10 **[ТС]**

Так об этом то и идёт речь.

Добавлено через 1 минуту

Сообщение от oleg-m1973

Что такое "ленивая синхронизация"? Я только обычную знаю.

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

@oleg-m1973 · 11.01.2021, 20:15

Сообщение от Дилендик

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

Чтобы пометить элемент, как удалённый, надо его сначала найти. Чтобы его найти, надо заблокировать весь список. Если ты всё равно блокируешь весь список, то сам бог велел не помечать элемент как удалённый, а просто удалить его.

@Дилендик · 11.01.2021, 20:33 **[ТС]**

Сообщение от oleg-m1973

Чтобы пометить элемент, как удалённый, надо его сначала найти. Чтобы его найти, надо заблокировать весь список. Если ты всё равно блокируешь весь список, то сам бог велел не помечать элемент как удалённый, а просто удалить его.

Я её не придумывала. Нам её надо использовать.

Не по теме:
_{Уже не первый раз ко мне обращаются на "ты". Понимаю, что форум демократичный, но немного цепляет. Я на ты общаюсь только с ближним кругом. Это просто мысли вслух. Не принимайте близко к сердцу. Будем считать, что я допустила Вас/тебя в ближний круг.}

@oleg-m1973 · 11.01.2021, 20:41

Сообщение от Дилендик

Не по теме:
Уже не первый раз ко мне обращаются на "ты". Понимаю, что форум демократичный, но немного цепляет. Я на ты общаюсь только с ближним кругом. Это просто мысли вслух. Не принимайте близко к сердцу. Будем считать, что я допустила Вас/тебя в ближний круг.

Не по теме:

Спасибо, конечно, за то, что сделали мне одолжение. Но, не стоит беспокоиться. Не буду больше мешать.

@Дилендик · 11.01.2021, 20:50 **[ТС]**

Простите не хотела обидеть. Мешать конечно не надо, а конструктивные предложения приветствуются.

@S_el · 12.01.2021, 00:55

Сообщение от Дилендик

И что делать? Мне то нужно ленивую синхронизацию применить. И многопоточность должна быть.
Что исправлять? Где смотреть?

Насколько я вижу, у вас в коде именно ленивая синхронизация. Код странный, есть какие-то причуды с реализацией:
Например,

C++
1
2
3
    LazySyncList() : head(new node(INT32_MIN)) {
        head->next = new node(INT32_MAX);
    }

зачем нужны такие ухищрения, если классический вариант с инициализацией нулевым указателем работает как положено.
Еще и близко не наблюдается очистка памяти - new выделяется, а про освобождение - забыли.
Еще надо инициализировать поля. Т.е. должно быть:

C++
1
 next(nullptr)

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

Лично мне кажется странным, что даже на 30 сообщении темы, не ясно в чем собственно вопрос.

@Дилендик · 12.01.2021, 01:01 **[ТС]**

Сообщение от S_el

Еще замер некорректный, логирование замерять не нужно, это мусор, влияющий на результат.

Вот Вы и ответили на вопрос. По результатам таблицы первой было ощущение, что что-то неправильно. Уверенности не было. Особенно после сравнения результата с таблицей 4.

Спасибо.

@S_el · 12.01.2021, 01:14

Сообщение от Дилендик

Вот Вы и ответили на вопрос. По результатам таблицы первой было ощущение, что что-то неправильно.

Есть еще кое-что, куда более важное, чем неучтенная операция логирования.
Самая большая нагрузка возникает из-за аллокации памяти, т.е. когда список растет. Проблема вашего кода в том, что при распределении на потоки, он n раз пытается засунуть в список набор от 0 до count/n
Естественно, так на интервалы делить нельзя, т.к. ваш список не может содержать дубликатов(т.к. реализует АСД множество).
Надо чтобы первый поток шел от 0 до count/n, второй от count/n до count/n до 2*count/n и.т.д.

Короче это надо исправлять и замерять еще раз.

@Дилендик · 12.01.2021, 01:45 **[ТС]**

Сообщение от S_el

Код странный

Главное было это узнать

Сообщение от S_el

есть какие-то причуды с реализацией

Легче "искать чёрную кошку в тёмной комнате", когда знаешь, что она там есть.

@GbaLog- · 12.01.2021, 12:35

Сообщение от oleg-m1973

Чтобы пометить элемент, как удалённый, надо его сначала найти. Чтобы его найти, надо заблокировать весь список.

ну, я думаю, это всё же не обязательно для поиска это делать: http://pages.di.unipi.it/ferra... 16/CP1.pdf
https://disco.ethz.ch/courses/... 8_2on1.pdf

@oleg-m1973 · 12.01.2021, 12:40

---

Новые блоги и статьи Все статьи Все блоги /
Администрация Хабра удаляет новые алгоритмы, которые не западно ориентированной философии кода, без уведомлений и объяснений. Hrethgir 20.06.2026 Делается это, как замечено, при правках - при объявлении концептуальных отличий в алгоримах. Делается это, по линейке событий - после дополнения публикации основными отличиями от основных западных. . .	Процесс ориентированная диалектика (не новость - просто системное обновление, философия). Hrethgir 20.06.2026 Однажды один участник в своём блоге, на этом форуме, сделал запись "О языках замолвите слово". Понимая, что язык - важная вещь, я решил хорошо подумать, прежде чем сказать, и сказал то, что вы видите. . .	Контроль уникальности строк в табличной части документа Maks 18.06.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ПланированиеСпецтехники" с табличной частью "НаличиеОборудования", разработанного в КА2. Задача: контроль уникальности строк в. . .	Клиент Uhbif79 18.06.2026 Здесь простой клиент для работы с сервером.
Сервер Uhbif79 18.06.2026 Выкладываю простейший сервер.	Дефенестрация kumehtar 18.06.2026 Узнал интересное слово. Дефенестрация. Это когда ты выбрасываешь кого-либо или что-либо из окна. Возьму на вооружение)))	Дихотомия добра и зла kumehtar 18.06.2026 Как Дзен-буддисты говорят о добре и зле: не нужно воевать против зла, нужно воевать против невежества. Тогда добро станет ествественным, и поэтому вечным. Но дело в том, что невежество всё время. . .	Своя Интернет-Компания iceja 18.06.2026 Я программист с экономическим образованием, пишу свой проект, это SaaS для бизнесов. Мне нужен co-founder с высшим экономическим образованием, и/ или инвестор. Сейчас проект в интенсивной разработке,. . .

@Дилендик 10 / 12 / 0 Регистрация: 20.07.2011 Сообщений: 430

	Может ли тестировании реализаций односвязного списка быть в 100 раз быстрее множества? 10.01.2021, 23:47. Показов 2675. Ответов 34 Метки многопоточность, структуры данных (Все метки) У меня несколько вопросов. 1. Может ли при тестировании реализаций односвязного списка и множества при синхронизации потоков, список проходить тестирование в 100 раз быстрее? Почему? 2. Может ли при ленивой синхронизации односвязного списка операция проверка проходить быстрее в два раза чем операция удаление? Почему? 0

@Дилендик 10 / 12 / 0 Регистрация: 20.07.2011 Сообщений: 430
	11.01.2021, 19:52 [ТС]
	Потоки 0

@Дилендик 10 / 12 / 0 Регистрация: 20.07.2011 Сообщений: 430
	11.01.2021, 20:50 [ТС]
	Простите не хотела обидеть. Мешать конечно не надо, а конструктивные предложения приветствуются. 0

@oleg-m1973 6772 / 4565 / 1844 Регистрация: 07.05.2019 Сообщений: 13,726
	12.01.2021, 12:40
	--- 0

Может ли тестировании реализаций односвязного списка быть в 100 раз быстрее множества?

Решение