ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Сравнение элементов массива
24 сообщений из 24, страница 1 из 1
Сравнение элементов массива
    #39139368
ukugyul552465
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ukugyul552465
Гость
Нужно сравнить элементы файла таким образом, чтобы узнать, нет ли в нём одинаковых элементов.
Файл:
100
200
356
899
125
...
Проблема заключается в том, что в файле может находится большое кол-во элементов.
...
Рейтинг: 0 / 0
28.12.2015, 15:02
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139372
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Отсортировать и сравнивать соседние.
...
Рейтинг: 0 / 0
28.12.2015, 15:04
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139377
ukugyul552465
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ukugyul552465
Гость
Т.е. сначала загрузить эти значения в массив, а затем отсортировать и сравнить соседние?
А сколько это будет занимать времени, если, к примеру, загрузка этих данных в массив длится около 7 минут?
...
Рейтинг: 0 / 0
28.12.2015, 15:06
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139392
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Скорость сортировки зависит от размера массива, объема реальной памяти и скорости проца.

PS Быстрее способа все равно нет.
...
Рейтинг: 0 / 0
28.12.2015, 15:16
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139407
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kolobok0
Участник
Dima T...PS Быстрее способа все равно нет.

это ложное утверждение.
если разрядность чисел входит в ворд - то можно тупо анализ на ноль хотя-бы одного в массиве.
туда-же вопрос про сортировку этих чисел...

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

(круглый)
...
Рейтинг: 0 / 0
28.12.2015, 15:32
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139419
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ukugyul552465Проблема заключается в том, что в файле может находится большое кол-во
элементов.
Наоборот, это не проблема, а решение. Как только размер файла превысил мощность множества
элементов, можно не глядя возвращать true.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
28.12.2015, 15:41
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139426
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kolobok0если разрядность чисел входит в ворд - то можно тупо анализ на ноль хотя-бы одного в массиве.
И как это спасет если, например, повторяется 1 ?

Если разрядность небольшая word (byte) то можно и не считая сказать что есть повторы если чисел больше 65536 (256).
...
Рейтинг: 0 / 0
28.12.2015, 15:46
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139463
ukugyul552465
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ukugyul552465
Гость
Числа типа unsigned long int.
Файл содержит от 1 миллиона до 100 миллионов чисел.
...
Рейтинг: 0 / 0
28.12.2015, 16:13
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139467
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
ukugyul552465Числа типа unsigned long int.
Файл содержит от 1 миллиона до 100 миллионов чисел.
Два способа решения:
1) Битовая маска размером 1/8 адресного пространства;
2) Сортировка (внутренняя или внешняя).

Первый быстрее, второй надёжнее.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
28.12.2015, 16:19
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139468
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
100 млн ~ 400 Мб. В память должно влезть. Сортировка думаю не более 3-5 сек. займет.
...
Рейтинг: 0 / 0
28.12.2015, 16:20
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139478
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Можно еще в несколько проходов проверять битовой маской интервалы значений, тогда на памяти маску будет уходить 512М/количество проходов.
...
Рейтинг: 0 / 0
28.12.2015, 16:30
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139494
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry Sibiryakov1) Битовая маска размером 1/8 адресного пространства;

+1 забыл я про бит-карту.

unsigned long int это 4 байта

При наличии 1 Гб адресного пространства покрывается весь диапазон. Так можно в один проход найти все повторы, быстрее сортировки будет. Можно предварительно первым проходом min/max найти, тогда память можно сэкономить (надо ((max - min) / 8) байт), но в худшем случае может оказаться 1 Гб. В лучшем случае 12,5 Мб. Хотя реально весь 1 Гб потребуется только при выделении памяти, в процессе работы в реальной памяти нужны будут только те страницы, которые будут использованы.
...
Рейтинг: 0 / 0
28.12.2015, 16:47
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139497
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima Tunsigned long int это 4 байта
Только для 32-х разрядных платформ.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
28.12.2015, 16:49
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139499
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Что-то туплю. Не 1 Гб, а 0,5 Гб. т.е. 2^32 / 8 = 512 Мб.
...
Рейтинг: 0 / 0
28.12.2015, 16:50
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139505
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima Tunsigned long int это 4 байта
Только для 32-х разрядных платформ.

Код: plaintext
1.
printf("%d\n", sizeof(unsigned long int));


MS VC 2015 при компиляции в x64 выдает 4.
...
Рейтинг: 0 / 0
28.12.2015, 16:53
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139512
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima TMS VC 2015 при компиляции в x64 выдает 4.
GCC на CentOS 64 бит выдаёт 8.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
28.12.2015, 17:00
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139546
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T100 млн ~ 400 Мб. В память должно влезть. Сортировка думаю не более 3-5 сек. займет.
Поскольку лишнее ложное срабатывание мы можем повторно проверить и отбросить,
вместо биткарты - можно взять карту Блума.
...
Рейтинг: 0 / 0
28.12.2015, 17:37
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139726
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
ukugyul552465Т.е. сначала загрузить эти значения в массив, а затем отсортировать и сравнить соседние?
А сколько это будет занимать времени, если, к примеру, загрузка этих данных в массив длится около 7 минут?


очевидно, не менее 14 минут...
...
Рейтинг: 0 / 0
29.12.2015, 06:00
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139859
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
MasterZivukugyul552465Т.е. сначала загрузить эти значения в массив, а затем отсортировать и сравнить соседние?
А сколько это будет занимать времени, если, к примеру, загрузка этих данных в массив длится около 7 минут?


очевидно, не менее 14 минут...
А если сразу B* дерево строить?
...
Рейтинг: 0 / 0
29.12.2015, 10:54
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139887
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
ukugyul552465Числа типа unsigned long int.
Файл содержит от 1 миллиона до 100 миллионов чисел.
Можно построить хоть целый лес, но 100 миллионов чисел вполне себе поместятся в памяти даже не слишком старых смартфонов. То есть грузим все, сортируем, ищем дубли. Деревья, фильтры Блума, битовые маски, разреженные маски и внешние сортировки в данном случае - просто способ развлечься.
...
Рейтинг: 0 / 0
29.12.2015, 11:30
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39139915
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А зачем всё грузить?
Нужно сравнить элементы файла таким образом, чтобы узнать, нет ли в нём одинаковых элементов.
Можно ли утверждать что нас интересуетс только факт наличия одинаковых элементов?
Результат true/false и при этом вычитывать до конца второй массив уж точно не нужно.
...
Рейтинг: 0 / 0
29.12.2015, 11:58
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39140128
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
maytonА зачем всё грузить?
чтобы действовать стандартным путём - предварительно вылить воду из чайника и свести задачу к предыдущей
...
Рейтинг: 0 / 0
29.12.2015, 15:40
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39140763
ukugyul552465
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ukugyul552465
Гость
Спасибо. Всё нормально получилось.
...
Рейтинг: 0 / 0
30.12.2015, 17:16
| Ответить | Цитировать | Написать  
Сравнение элементов массива
    #39144204
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Какая в итоге асимптотика получилась ?
...
Рейтинг: 0 / 0
11.01.2016, 03:17
| Ответить | Цитировать | Написать  
24 сообщений из 24, страница 1 из 1
Форумы / C++ [игнор отключен] [закрыт для гостей] / Сравнение элементов массива
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]