ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Различные структуры данных. Реализация
25 сообщений из 422, страница 13 из 17
  13  все
Различные структуры данных. Реализация
    #39036184
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercury2. Для запуска программы на Java требуется виртуальная машина.

Существуют лаунчеры позволяющие запускать java-приложение просто как exe-шник. С точки
зрения Windows-пользователя он абсолютно ничем не отличается от обычного бинарника. На
такой технологии построены к примеру среда разработки IntellijIdea и Torrent-клииент Azureus/Vuze.

И вообще любая мало-мальски сложная задача через некоторое время порождает в техническом
задании целый слой рантайма с RTTI и мета-описателями который можно с успехом категоризировать
как виртуальную машину. Свои вирт. машины есть в AutoCad, Basic, Веб-браузерах, продуктах
MS, в средах разработки Perl, PHP, Python, и RPG-играх (Lua/Python).

Поэтому я-бы не стал акцентировать на ВМ так сильно. Скорее другой вопрос интересен. Возможно
ли современное прогрессивное программирование только на классической модели "исходник-бинарь"?
...
Рейтинг: 0 / 0
26.08.2015, 10:50
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39036275
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Мне непонятен акцент на "описывать алгоритмы". В чем проблема описания?
Половина алгоритмов дискретной математики описана на Modula/ADA/Pascal.
На языках по сути мёртвых в наше время. В знаменитом многотомнике Кнута
алгоритмы описывались в виде формул либо в виде ПО Ассемблера к гипотетической
виртуальной машине. Во всех совестских книжках (до 1980 прибл) численные
методы описаны мат.формулой или блок схемой или АЯ или его бох весть
каким способом.

Поэтому для меня проблемы "описания" алгоритмов не существует. Их
можно описывать на чём угодно и как угодно. Главное чтобы договорённости
об аппарате описания были одинаково понятны для писателя и читателя.
...
Рейтинг: 0 / 0
26.08.2015, 12:37
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39036366
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton, petrav

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

кстати, перевод алгоритма на другой язык очень помогает в его понимании
...
Рейтинг: 0 / 0
26.08.2015, 13:50
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39036825
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
SashaMercuryЯ сказал
1. Java объектно-ориентированный язык.
2. Для запуска программы на Java требуется виртуальная машина.
3. Это влияет на требование к ресурсам.
И ничего более не сказал, ничего лишнего не сказал. То о чём вы говорите, детали, которые не опровергают 3 пункта написанных выше и не влияют на общую картину.1. Java не язык, Java - платформа. Это факт, которого вы не понимаете;
2. Требуется. Языков и систем, использующих виртуальные машины - много. Не факт - банальность.;
3. Системные требования встраиваемых JVM - 32Мб. Тот же ruToken Pro и аналоги обходятся, как я понимаю и меньшим.
С другой стороны, у AzulSystems есть реальный пример системы, где JVM исполняет приложение с, примерно, терабайтной кучей. Года три-четыре назад это было "всего" четверть терабайта.
Так что с ресурсами - ни о чём вообще.Критика должна быть конструктивной, замечания чёткими, понятными и по существу.Чтобы понимать ответ нужен некий базовый фундамент. А вы, уж простите, балансируете на верхушке незабитой сваи и радуетесь, что так высоко залезли.
...
Рейтинг: 0 / 0
26.08.2015, 19:10
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39036836
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Basil A. SidorovС другой стороны, у AzulSystems есть реальный пример системы, где JVM исполняет приложение с, примерно, терабайтной кучей. Года три-четыре назад это было "всего" четверть терабайта.
Несколькими топиками выше мне кажется я начинаю понимать что наш пассажир кивает
то на MemModel/GC, то на VM ссылаясь на аспект т.н. "реального времени". Забавно но я специально
сидел и пытался вспомнить хотя-бы одно ТЗ из своих С++ - ных где-бы факт реалтаймовости
был отражён хотя-бы тезисно. Но... ничего не могу вспомнить. Не было таких. При том что
у меня достаточно много друзей - эмбедщиков кодорые кодят свои микро-контроллеры
на С но и в их предметной области есть нюансы. И ни один из них не делился со мной проблемами
перформанса или латентности. У них другие бока были. Вообще не в этой плоскости.
...
Рейтинг: 0 / 0
26.08.2015, 19:27
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39038737
White Owl
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
White Owl
Участник
Модератор: Для желающих продолжать идите сюда: http://www.sql.ru/forum/1172924/o-primenimost-yazykov
Все новые посты не относящиеся к теме топика будут убиваться сразу.
...
Рейтинг: 0 / 0
28.08.2015, 17:34
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074152
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Здравствуйте.
Подскажите пожалуйста, существует ли структура данных(организована линейно) со следующими характеристиками:
1. Поиск индекса минимального/максимального элемента
2. Удаление элемента
Почему я говорю о линейной организации, по той причине что мне необходимо знать сколько элементов 'слева' и 'справа' от минимального/максимального.

Может быть подойдёт обыкновенный непрерывный массив, но проблема с удалением элемента, слишком долго и слишком часто будет выполняться эта операция.
PS
Предполагаю, что существуют типы данных из STL удовлетворяющие моим требованиям, но не уверен.
...
Рейтинг: 0 / 0
12.10.2015, 09:04
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074187
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Связный список (std::list) не подойдет?
Поиск O(N) - обычный перебор.
Удаление O(1) - правка ссылок в соседних элементах.
...
Рейтинг: 0 / 0
12.10.2015, 09:36
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074207
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Да, у меня опечатка, поиск . Писал про поиск, а думал про сортировку.

Дмитрий, не подойдёт. Как я узнаю сколько элементов справа и сколько слева. Множество элементов будет многократно обновляться(после удаления элементов)
...
Рейтинг: 0 / 0
12.10.2015, 09:53
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074220
mcureenab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mcureenab
Участник
SashaMercuryДа, у меня опечатка, поиск . Писал про поиск, а думал про сортировку.

Дмитрий, не подойдёт. Как я узнаю сколько элементов справа и сколько слева. Множество элементов будет многократно обновляться(после удаления элементов) У тебя нет требований к функции расчета смещения, поэтому можно просто сканировать весь список.
Если оптимизировать, то надо хранить смещения Min и Max элементов и размер списка. А по мере добавления элементов в список левее или правее Min и левее или правее Max, обновлять эту вспомогательную структуру.
...
Рейтинг: 0 / 0
12.10.2015, 10:02
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074233
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
mcureenab,
никакие элементы в список не добавляются. Один раз добавятся и всё. Дальше будут только удаляться. В цикле. На каждой итерации цикла мне нужно искать минимальный элемент и мне необходимо узнать сколько элементов от него слева. Удаляю этот элемент и проделываю аналогичные действия. Итерации продолжаются пока есть элементы
...
Рейтинг: 0 / 0
12.10.2015, 10:22
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074235
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
mcureenab
У тебя нет требований к функции расчета смещения
...
Рейтинг: 0 / 0
12.10.2015, 10:24
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074237
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДа, у меня опечатка, поиск . Писал про поиск, а думал про сортировку.

Дмитрий, не подойдёт. Как я узнаю сколько элементов справа и сколько слева. Множество элементов будет многократно обновляться(после удаления элементов)
Просто посчитаешь перебором.
Или зная порядковый номер элемента (если нашел перебором, то он известен) и размер списка - легко считается сколько справа/слева.

Ты бы лучше задачу поподробней описал. Телепатов тут нет, откуда нам знать что еще тебе надо кроме того что ты написал.
Большинство сложных задач не имеет универсального решения. Исходить надо из конкретной задачи, смотреть какие операции чаще надо выполнять, их оптимизировать в первую очередь. Скорее всего потребуется не одна структура, а несколько: в основной данные, в дополнительных метаданные для ускорения работы с данными. Возможно есть смысл алгоритм перестроить.
...
Рейтинг: 0 / 0
12.10.2015, 10:31
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074261
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercurymcureenab,
никакие элементы в список не добавляются. Один раз добавятся и всё. Дальше будут только удаляться. В цикле. На каждой итерации цикла мне нужно искать минимальный элемент и мне необходимо узнать сколько элементов от него слева. Удаляю этот элемент и проделываю аналогичные действия. Итерации продолжаются пока есть элементы
Тут лучше вместо удаления заменять на несуществующее значение. И использовать обычные массивы.

Делаешь обычный массив значений.
Делаешь второй массив из указателей на значения. Сортируешь второй по *значение. Т.е. получаешь в каком порядке выбирать из первого.
Идешь по второму, на каждом шаге в первом выбранное заменяешь на недействительное и считаешь вправо или влево (куда ближе) сколько осталось действительных.

Дальше можно оптимизировать подсчет действительных третьим массивом. Делаешь массив счетчиков, например каждый счетчик на группу 256 элементов. Удаляя - уменьшаешь счетчик группы на 1. Для подсчета остается посчитать сколько внутри группы слева, а затем прибавить счетчики всех полных групп слева. Размер элементов в группе подбирать опытным путем.
...
Рейтинг: 0 / 0
12.10.2015, 10:58
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074281
mcureenab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mcureenab
Участник
Dima TSashaMercuryДа, у меня опечатка, поиск . Писал про поиск, а думал про сортировку.

Дмитрий, не подойдёт. Как я узнаю сколько элементов справа и сколько слева. Множество элементов будет многократно обновляться(после удаления элементов)
Просто посчитаешь перебором.
Или зная порядковый номер элемента (если нашел перебором, то он известен) и размер списка - легко считается сколько справа/слева.
Да. Из вспомогательных данных, тут только размер списка нужен, чтобы узнать сколько элементов осталось справа.

Если на min элемент выходить по индексу, то после его удаления придется как-то актуализировать позиции "сдвинувшихся" элементов.
...
Рейтинг: 0 / 0
12.10.2015, 11:18
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074336
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercurymcureenab,
никакие элементы в список не добавляются. Один раз добавятся и всё. Дальше будут только удаляться. В цикле. На каждой итерации цикла мне нужно искать минимальный элемент и мне необходимо узнать сколько элементов от него слева. Удаляю этот элемент и проделываю аналогичные действия. Итерации продолжаются пока есть элементы
Требование O(1) на удаление - слишком суровое. Дело в том что даже со списком
надо будет актуализировать счетчики "количества слева".

Подумай о компромиссах.
...
Рейтинг: 0 / 0
12.10.2015, 12:02
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074340
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Если упростить задачу, то у нас есть неупорядоченный массив с уникальными элементами. Для каждого элемента мне нужно определить сколько элементов до него(слева от него) больше него. Асимптотика n^2 и выше меня не устраивает
...
Рейтинг: 0 / 0
12.10.2015, 12:05
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074343
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
МаркДело в том что даже со списком
надо будет актуализировать счетчики "количества слева"

Вот вот
...
Рейтинг: 0 / 0
12.10.2015, 12:07
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074366
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryЕсли упростить задачу, то у нас есть неупорядоченный массив с уникальными элементами. Для каждого элемента мне нужно определить сколько элементов до него(слева от него) больше него. Асимптотика n^2 и выше меня не устраивает
Мой вариант читал? 18266267
Dima T ... Делаешь массив счетчиков, например каждый счетчик на группу 256 элементов. Удаляя - уменьшаешь счетчик группы на 1. Для подсчета остается посчитать сколько внутри группы слева, а затем прибавить счетчики всех полных групп слева. Размер элементов в группе подбирать опытным путем.
Не O(1) но меньше чем n^2

В принципе можно построить бинарное дерево, где каждый узел содержит количество подузлов. Тогда при удалении надо будет уменьшить log2(N) счетчиков. И для подсчета перебрать log2(N). Т.е. общая сложность будет N*log2(N)
...
Рейтинг: 0 / 0
12.10.2015, 12:24
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074390
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ребята. Тема структур данных - интересная и бесконечная. Можно смотреть в сторону отложенных
калькуляций или версионностей и получить на этом еще больше перформанса.

Но лучше идти от ТЗ. Особенно в части статистики. К примеру будет 1 миллиард
элементов в списке. Будет удалено примерно 100 млн. И будет 200 млн поисков.
Можно даже рассмотреть промахи поиска и удалений и сыграть на этом.

Промоделлить это и выбрать лучшую структуру.

Мне кажется такой подход - продуктивнее.
...
Рейтинг: 0 / 0
12.10.2015, 12:51
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074399
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Как я понял ТЗ такое:
SashaMercuryникакие элементы в список не добавляются. Один раз добавятся и всё. Дальше будут только удаляться. В цикле. На каждой итерации цикла мне нужно искать минимальный элемент и мне необходимо узнать сколько элементов от него слева. Удаляю этот элемент и проделываю аналогичные действия. Итерации продолжаются пока есть элементы
Или почти тоже самое другими словами
SashaMercuryЕсли упростить задачу, то у нас есть неупорядоченный массив с уникальными элементами. Для каждого элемента мне нужно определить сколько элементов до него(слева от него) больше него.
...
Рейтинг: 0 / 0
12.10.2015, 12:59
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074443
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercurymcureenab,
никакие элементы в список не добавляются. Один раз добавятся и всё. Дальше будут только удаляться. В цикле. На каждой итерации цикла мне нужно искать минимальный элемент и мне необходимо узнать сколько элементов от него слева. Удаляю этот элемент и проделываю аналогичные действия. Итерации продолжаются пока есть элементы
Тут лучше вместо удаления заменять на несуществующее значение. И использовать обычные массивы.

Делаешь обычный массив значений.
Делаешь второй массив из указателей на значения. Сортируешь второй по *значение. Т.е. получаешь в каком порядке выбирать из первого.
Идешь по второму, на каждом шаге в первом выбранное заменяешь на недействительное и считаешь вправо или влево (куда ближе) сколько осталось действительных.

Дальше можно оптимизировать подсчет действительных третьим массивом. Делаешь массив счетчиков, например каждый счетчик на группу 256 элементов. Удаляя - уменьшаешь счетчик группы на 1. Для подсчета остается посчитать сколько внутри группы слева, а затем прибавить счетчики всех полных групп слева. Размер элементов в группе подбирать опытным путем.

К сожалению будем иметь
...
Рейтинг: 0 / 0
12.10.2015, 13:40
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074445
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Не получится заменять каждый элемент недействительным, к сожалению. Конечно я об этом подумал
...
Рейтинг: 0 / 0
12.10.2015, 13:41
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074481
mcureenab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mcureenab
Участник
SashaMercuryЕсли упростить задачу, то у нас есть неупорядоченный массив с уникальными элементами. Для каждого элемента мне нужно определить сколько элементов до него(слева от него) больше него. Асимптотика n^2 и выше меня не устраиваетЭто как то уж очень упрощенно и очевидно. Получается нужно один раз пройти список подсчитывая количество просмотренных элементов и каждому элементу списка присвоить текущее значение счетчика.

Но каждое удаление элемента приведет к сдвигу хвоста списка. В массиве, это сдвиг элементов, в односвязном списке это перенумерация элементов. Думаю, в этом смысле альтернатив нет.

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

Или перед удалением пробегать всю голову, но сравнивая ключ.

Трудно сказать что быстрее. От данных зависит.
...
Рейтинг: 0 / 0
12.10.2015, 14:19
| Ответить | Цитировать | Написать  
Различные структуры данных. Реализация
    #39074483
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryК сожалению будем иметь
Это если сделать только то что ты красным выделил. Если сделать с группами - будет быстрее. Например К размер группы, тогда для подсчета надо перебрать: К/2 (внутри группы) + N/2K (количество целых групп). Остается подобрать такое К чтобы К/2+N/2K было минимальным. Если добавить что К=2^M (чтобы считать быстрее) то подбор несложный.
Если с деревом 18266267 то Тут по сути группирование групп в несколько уровней.
SashaMercuryНе получится заменять каждый элемент недействительным, к сожалению. Конечно я об этом подумал
Почему? Есть еще какие-то условия или просто значений не хватает? Если не хватает - то минимально допустимое. Оно используется только на первом шаге, затем оно не встречается.
...
Рейтинг: 0 / 0
12.10.2015, 14:20
| Ответить | Цитировать | Написать  
25 сообщений из 422, страница 13 из 17
  13  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Различные структуры данных. Реализация
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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