Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Слить куски в один / 8 сообщений из 8, страница 1 из 1
07.08.2013, 09:17
    #38357742
Poppler
Poppler
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
Есть массив int размером скажем в 132 элемента, в котором находятся отсортированные куски размером 33 друг за другом т.е. первый отсортированный кусок занимает позицию с 0 до 33, второй с 33 до 66, третий с 66 до 99 и т.д.
Нужно слить эти куски в один отсортированный большой кусок в этом же самом массиве.
Как бы это покрасивее сделать, чтобы памяти минимум потреблял и скорость бы не просела?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2013, 09:24
    #38357751
Poppler
Poppler
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
Причём в последнем куске может быть не равное 33 количество элементов, а скажем на один или два больше. Длина массива известна и размер кусков кроме последнего тоже известен, размер последнего легко вычисляется.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2013, 10:00
    #38357794
?
?
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
inplace_merge
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.08.2013, 14:45
    #38358361
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
? inplace_merge
Там времено выделяется еще 132 или элемента. А может стоит запилить
сортировку "по месту" ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.08.2013, 00:05
    #38358994
Mozok
Mozok
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
mayton? inplace_merge
Там времено выделяется еще 132 или элемента. А может стоит запилить
сортировку "по месту" ?
Нет, не выделяется.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.08.2013, 00:11
    #38358996
Mozok
Mozok
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
Mozok,

Поправлю сам себя для строгости - не обязана выделятся.
Как разработчики библиотеки решат, так и будет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.08.2013, 14:03
    #38359661
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
Mozokmaytonпропущено...

Там времено выделяется еще 132 или элемента. А может стоит запилить
сортировку "по месту" ?
Нет, не выделяется.
Ну тогда это круть несусветная. И память не выделяет и способствует росту волос.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.08.2013, 16:21
    #38359954
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Слить куски в один
maytonНу тогда это круть несусветная. И память не выделяет и способствует росту волос.
Так по ссылке же написано, что при выделении памяти - O(N), а без памяти - N*log(N)
Так что все имеет цену :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Слить куски в один / 8 сообщений из 8, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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