Оптимальная сортировка при тяжелом присваивании
А что-нибудь помешает завести массив индексов, отсортировать его, а уже потом с его помощью переупорядочить массив?
присваивание то тяжелое, а сравнение?
сравнение элементов по скорости такое же как и сравнение целых чисел
вобщем, можно считать мгновенно
вобщем, можно считать мгновенно
переупорядочить массив?это как?
у меня знания по информатике и алгоритмам хромают очень
всмысле, что такое переупорядочивание - в общем смысле понятно, но в данном случае...
Тебе достаточно, если у тебя будет отсортированный массив ссылок на эти элементы?
Я могу себе представить что-то вроде:
1) Заводим карту сравнений n*n (diff[i][j] = 0, если i и j элементы исходного массива равны, -1, если i элемент меньше, 1, если больше).
2) Заводим новый массив размера n, с значениями 1, 2, ... n.
3) Упорядочиваем новый массив, используя вместо обычного сравнения сравнение по карте.
4) В соответствии с порядком этого нового массива, заводим массив "отсортировано", в который в нужном порядке складываем значения из исходного массива.
Общая сложность - порядка (размер исходного массива)*(сложность присваивания).
1) Заводим карту сравнений n*n (diff[i][j] = 0, если i и j элементы исходного массива равны, -1, если i элемент меньше, 1, если больше).
2) Заводим новый массив размера n, с значениями 1, 2, ... n.
3) Упорядочиваем новый массив, используя вместо обычного сравнения сравнение по карте.
4) В соответствии с порядком этого нового массива, заводим массив "отсортировано", в который в нужном порядке складываем значения из исходного массива.
Общая сложность - порядка (размер исходного массива)*(сложность присваивания).
Ага, и n^2 сравнений, если они тоже тяжелые.
А если они легкие (как автор, собственно, и написал несколькими сообщениями выше то непонятно зачем городить эту муть с картой сравнений.
А если они легкие (как автор, собственно, и написал несколькими сообщениями выше то непонятно зачем городить эту муть с картой сравнений.
неа, недостаточно
тут еще проблема есть в том, что возможны ситуации, когда временный объект не получится создать и будет доступен только своп (своп работает без временных объектов)
тут еще проблема есть в том, что возможны ситуации, когда временный объект не получится создать и будет доступен только своп (своп работает без временных объектов)
Ладно... меньше абстракций, больше конкретики: элементы массива - разделы на диске
Что понимается под "присваиванием" разделов ?
копирование содержимого
вообще, основной операцией тут является своп, алгоритм которого уже имеется (правда с доп. условиями, ну да хрен с ними)
копирование раздела если и осуществляется, то на свободное место на диске если такое имеется
вообще, основной операцией тут является своп, алгоритм которого уже имеется (правда с доп. условиями, ну да хрен с ними)
копирование раздела если и осуществляется, то на свободное место на диске если такое имеется
Кол-во элементов - порядка 10Идея (возможно уже высказывалась ранее): сортируем, а только потом начинаем присваивать.
Присваивание работает долго и разбрасываться ими очень неразумно
Какой алгортим лучше использовать?
Хинт: в неотсортированной последовательности с большой вероятностью будут содержаться уже отсортированные подпоследовательности из ~2-3 элементов
Детали: пусть нам надо отсортировать A[i] длины N.
1. Берем массив B[i] и заполняем его числами 0, 1, 2, 3, ... N-1.
2. Сортируем B, однако в качестве функтора сравнения выступает A[B[i]] ? A[B[j]].
3. После того, как отсортировали, формируем список присваиваний, которые надо сделать.
4. Делаем не более, чем 3N/2 присвоений. Мб даже меньше, если какие-то элементы остались на месте.
Есть возможность использовать буфер? И насколько большой?
Размеры этих объектов примерно одинаковы? Или наоборот, могут различаться в разы/на порядки?
Размеры этих объектов примерно одинаковы? Или наоборот, могут различаться в разы/на порядки?
4. Делаем не более, чем 3N/2 присвоений. Мб даже меньше, если какие-то элементы остались на месте.У него есть swap, значит N-1 swap-ов.
Осознал
Мне даже со свопом действительно проще будет
Мне даже со свопом действительно проще будет
маза по скорости swap вероятнее всего будет работать как 2 присваивания, т.е. это даже хуже. Но, как и было заявлено, бывают плохие ситуации, когда temp-а нет.
Наличие буфера и его размер - как повезет
Размеры объектов разные, но свопу это не мешает.
Размеры объектов разные, но свопу это не мешает.
Ну свап - тоже буфер.
То есть любой объект в свап помещается?
Надеюсь это не реальные разделы на диске?
Иначе там простым присвоением не отделаешься
То есть любой объект в свап помещается?
Надеюсь это не реальные разделы на диске?
Иначе там простым присвоением не отделаешься
Свап буфер юзает, но свапу может хватить такого буфера, в который раздел и не вместится.
Свап хитроумный, работающий в экстремальных условиях
> Надеюсь это не реальные разделы на диске?
надейся
Свап хитроумный, работающий в экстремальных условиях
> Надеюсь это не реальные разделы на диске?
надейся
В общем такое называется дефрагментацией - попробуй поискать алгоритмы работы дефрагментаторов (а то и какой-нибудь с открытым кодом).
Блин, я изначально вопрос неправильно поставил, упомянув про присваивание и временные объекты, хотя основной операцией будет своп, который формально можно считать не использует буфер.
Да в принципе проблему считаю решенной. Буду юзать индексы, а потом переупорядочивание либо со свопом либо с временными объектами в зависимости от ситуации
Да в принципе проблему считаю решенной. Буду юзать индексы, а потом переупорядочивание либо со свопом либо с временными объектами в зависимости от ситуации
Ну или вот кратко:
1. Сортируешь ссылки на разделы
2. Создаешь новую карту диска (то есть в отсортированном порядке с учетом размеров)
2.1. Отмечаешь разделы, которые останутся на своем месте и не трогаешь их вообще (в том числе в п.3)
3. Проводишь копирование кусков с учетом буфера
1. Сортируешь ссылки на разделы
2. Создаешь новую карту диска (то есть в отсортированном порядке с учетом размеров)
2.1. Отмечаешь разделы, которые останутся на своем месте и не трогаешь их вообще (в том числе в п.3)
3. Проводишь копирование кусков с учетом буфера
маза, гораздо интереснее не порядок определить, а правильное смещение каждого раздела при уже найденном новом порядке. здесь есть что оптимизировать для ускорения всей сортировки)
если не секрет, то в какой задаче могло понадобиться сортировать разделы?
если не секрет, то в какой задаче могло понадобиться сортировать разделы?
Чем своп от буфера отличается?
Или это реальный своп оси?
Тогда почему нельзя использовать озу? Из-за угрозы потери данных?
Или это реальный своп оси?
Тогда почему нельзя использовать озу? Из-за угрозы потери данных?
в какой задаче могло понадобиться сортировать разделы?спроси у , где он работает
ответ на твой вопрос скрыт в названии фирмы
маза, гораздо интереснее не порядок определить, а правильное смещение каждого раздела при уже найденном новом порядке.
После сортировки ссылок и на основании инфы о размерах разделов это вычисляется.
здесь есть что оптимизировать для ускорения всей сортировки
А что можно оптимизировать, кроме случая, когда раздел останется на том же месте?
> После сортировки ссылок и на основании инфы о размерах разделов это вычисляется.
это возможно, если разделы вплотную стоят друг к другу.
на диске могут быть unallocated spaces
>А что можно оптимизировать, кроме случая, когда раздел останется на том же месте?
сдвиг раздела на небольшое расстояние гораздо быстрее делается, нежели его полное копирование в новое место.
это возможно, если разделы вплотную стоят друг к другу.
на диске могут быть unallocated spaces
>А что можно оптимизировать, кроме случая, когда раздел останется на том же месте?
сдвиг раздела на небольшое расстояние гораздо быстрее делается, нежели его полное копирование в новое место.
спроси у , где он работает, ты где работаешь?
на самом деле вопрос был о задаче, а не о месте работы.
в акронисе :-
Ребят, есть много чего написать и могу полностью сформулировать задачу, но начинаю писать и понимаю, что много писать придется =)
Могу через день-два проапать тред с более полной инфой.
Пока всем спасибо за обсуждение и реальные советы, буду трудиться дальше :-)
Ребят, есть много чего написать и могу полностью сформулировать задачу, но начинаю писать и понимаю, что много писать придется =)
Могу через день-два проапать тред с более полной инфой.
Пока всем спасибо за обсуждение и реальные советы, буду трудиться дальше :-)
на диске могут быть unallocated spaces
Чем они отличаются от разделов?
Разве что тем, что их можно не учитывать при сортировке.
сдвиг раздела на небольшое расстояние гораздо быстрее делается, нежели его полное копирование в новое место.
Это только при условии, если есть буфер, куда можно запихнуть всю разницу + при это м должно оставаться хоть немного места на буфер копирования.
Ну или там должно быть unallocated spaces.
В общем-то можно учитывать такое при сортировке, но боюсь, что так будет редко.
смешно, но я тоже там работаю 
где конкретно? 
у каткова
гы
я с disk manager-ом ковыряюсь у Зорина
я с disk manager-ом ковыряюсь у Зорина
Чем они отличаются от разделов?это не разделы. ими надо пользоваться.
Это только при условии, если есть буфер, куда можно запихнуть всю разницу + при это м должно оставаться хоть немного места на буфер копирования.буфер не нужен.
разделы копируются на файловом уровне.
я к вам тортик заносил недавно
ты не попробовал?:)
ты не попробовал?:)
гм... последний раз тортик нам кто-то заносил месяц назад, помоему
ну, за исключением того, что 5 минут назад нам hr принесла тортег с поздравлениями с др нашего сотруднечга
я все тортики хаваю, ибо нахоляву
ну, за исключением того, что 5 минут назад нам hr принесла тортег с поздравлениями с др нашего сотруднечга
я все тортики хаваю, ибо нахоляву
Вот пример алгоритма для частного случая, когда размер буфера является НОДом размеров всех разделов(например если размеры всех разделов в Мб - буфер = 1Мб, но лучше выбирать его как можно больше, но его должно хватать и на хранение одного куска данных, и на все накладные расходы):
1. Сортируешь ссылки на разделы
2. Нумеруешь разделы в порядке сортировки
3. Разбиваешь все разделы на куски размера буфера и нумеруешь их двумя индексами: 1-й - порядок сортировки, 2-й - номер куска в разделе
В результате у тебя получается задача сортировки этих пар номеров, для которой тебе нужно взять любой метод сортировки, который минимизирует число перестановок (так сразу метод не подскажу, но тут наверняка есть гуру, которые сразу посоветуют).
4. Сортируешь этим методом куски из п.3
Все
1. Сортируешь ссылки на разделы
2. Нумеруешь разделы в порядке сортировки
3. Разбиваешь все разделы на куски размера буфера и нумеруешь их двумя индексами: 1-й - порядок сортировки, 2-й - номер куска в разделе
В результате у тебя получается задача сортировки этих пар номеров, для которой тебе нужно взять любой метод сортировки, который минимизирует число перестановок (так сразу метод не подскажу, но тут наверняка есть гуру, которые сразу посоветуют).
4. Сортируешь этим методом куски из п.3
Все
буфер не нужен.
разделы копируются на файловом уровне.
Это как это так?
Или используется буфер винта/контроллера?
>Присваивание работает долго и разбрасываться ими очень неразумно
>у меня знания по информатике и алгоритмам хромают очень
>в акронисе
Никогда не куплю ничо из их продуктов, и другим отсоветую
>у меня знания по информатике и алгоритмам хромают очень
>в акронисе
Никогда не куплю ничо из их продуктов, и другим отсоветую
ты хотя б виндовс лицензионный купил?
а купишь ты или нет что-нибудь, что в акронисе делают - мало волнует
а купишь ты или нет что-нибудь, что в акронисе делают - мало волнует
Никогда не куплю ничо из их продуктов, и другим отсоветуюгыгы
а ты знаком с тем, как разрабатывается софт? У любого программиста есть вопросы, ответы на которые он не знает. Хорошие программисты эти ответы получают, например, спросив у коллег или, если вопрос технологического плана, то прочитав документацию. Плохие программисты молча делают плохое решение.
Зная -а в течение более, чем 10 лет, могу сказать, что он хороший программист. А еще то, что "у меня знания по информатике и алгоритмам хромают очень" слегка черезчур самокритичное высказывание. Именно от -а я научился ряду прикольных алгоритмов, которые не знал до этого. И вообще, рюхает.
И продукты Acronis отличные!
от -а я научился ряду прикольных алгоритмов, которые не знал до этогоно все-таки -у не помешало бы заботать Кнута и осла....
да, обновить знания стоит. Все-таки за десять лет даже простые вещи могут забываются.
Никогда не куплю ничо из их продуктов, и другим отсоветуювесь софт так пишут
времена такие
и так в принципе во всем
при минимальной цене конечного продукта и при минимальном времени разработки сделать ту же функциональность что у конкурентов
машины раньше афигенные были, а щас в любой новой тачке косяки встречаются
Зная -а в течение более, чем 10 лет, могу сказать, что он хороший программист.причем тут 10 лет?
это все равно субъективное мнение
машины раньше афигенные былиВ Советские Времена?
в римской империи
Оставить комментарий
okunek
Кол-во элементов - порядка 10Присваивание работает долго и разбрасываться ими очень неразумно
Какой алгортим лучше использовать?
Хинт: в неотсортированной последовательности с большой вероятностью будут содержаться уже отсортированные подпоследовательности из ~2-3 элементов