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

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

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

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

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

Если разрядность небольшая word (byte) то можно и не считая сказать что есть повторы если чисел больше 65536 (256).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2015, 16:13
    #39139463
ukugyul552465
ukugyul552465
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение элементов массива
Числа типа unsigned long int.
Файл содержит от 1 миллиона до 100 миллионов чисел.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2015, 16:19
    #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:20
    #39139468
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение элементов массива
100 млн ~ 400 Мб. В память должно влезть. Сортировка думаю не более 3-5 сек. займет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2015, 16:30
    #39139478
wst
wst
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение элементов массива
Можно еще в несколько проходов проверять битовой маской интервалы значений, тогда на памяти маску будет уходить 512М/количество проходов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2015, 16:47
    #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:49
    #39139497
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение элементов массива
Dima Tunsigned long int это 4 байта
Только для 32-х разрядных платформ.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2015, 16:50
    #39139499
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение элементов массива
Что-то туплю. Не 1 Гб, а 0,5 Гб. т.е. 2^32 / 8 = 512 Мб.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
28.12.2015, 16:53
    #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, 17:00
    #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:37
    #39139546
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение элементов массива
Dima T100 млн ~ 400 Мб. В память должно влезть. Сортировка думаю не более 3-5 сек. займет.
Поскольку лишнее ложное срабатывание мы можем повторно проверить и отбросить,
вместо биткарты - можно взять карту Блума.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
29.12.2015, 06:00
    #39139726
MasterZiv
MasterZiv
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сравнение элементов массива
ukugyul552465Т.е. сначала загрузить эти значения в массив, а затем отсортировать и сравнить соседние?
А сколько это будет занимать времени, если, к примеру, загрузка этих данных в массив длится около 7 минут?


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


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


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