Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Не пойдет. Substr тоже занимает O(M) (где M — длина вырезки), копировать-то надо. Но там длина подстроки вычисляется элементарно, а тут — нет.
Бр-р. Вообще-то, Split точно так же работает через Substr. И длина, естественно, вычисляется элементарно.
PD>Ты просил пример, где нужно больше O(1), я его тебе дал. Никаких других условий не было. А если добавлять условия по ходу действия, то мы никогда не кончим.
Не нужно здесь больше O(1). В тот момент, когда мы порождаем новую строку для result, мы [i]уже знаем длину — потому, что мы к этому моменту нашли сепаратор.
PD>Все, Антон, закрываю со своей стороны эту веточку. Мне дискуссии с тобой насчет строк уже изрядно надоели
Учиться, Павел, никогда не поздно. Если, конечно, не вставать в позу "вы все зашоренные, а я один знаю как правильно".
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[52]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>То есть я тебе дал не реальную задачу, а некоторую модификацию. Чтобы тебе скучно не было.
Но, тем не менее, мне было скучно.
K>>Парсинг CSV — задача имеющая тривиальное решение. Вся работа в вашей задаче связана с разработкой структуры размещения читаемого файла в памяти. Которая после создания не изменяется. PD>Вполне согласен. Но asciiz меня здесь спасли. В сущности, твое решение ничем от моего не отличается. Поэтому я специально в пятницу не торопился выкладывать свое, ждал, что ты сделаешь один шаг, дойдешь до ASCIIZ, и мне останется только поздравить тебя с решением . Но тебе признать формат ASCIIZ религия не позволяет
Отличается принципиально. Я занимаюсь парсингом CSV один раз, а вы, фактически, парсите поток байтов, разделенных, извините за каламбур, разделителями каждый раз при чтении строки таблицы, хранящейся в памяти.
PD>Нельзя. Давай не будем это обсуждать. Есть причины, которые я не могу раскрывать.
Не так страшно раскрыть причины, как отсутствие причин.
PD>Исключительно из требований конкретной задачи. Я пойду на нарушение любых канонов, если в данной задачае это будет оправданно.
Не нужно подменять понятия. "Следование канонам" и разумный выбор на основании имеющейся информации — разные вещи. И если человек не может объяснить из каких соображений он выбирает структуры данных, это может означать не столько то, что он не желает следовать каким-то там "канонам" сколько то, что он просто не понимает, что он делает.
PD>Странный вопрос. Тебе объяснить про N^2 и NlnN ?
Не страннее остального треда. Т.е. разница между N^2 и N log N вам понятна, а разница между 1 и N и между N и log N — не понятна? А если понятна, то зачем весь этот разговор?
... << RSDN@Home 1.2.0 alpha 4 rev. 1228>>
'You may call it "nonsense" if you like, but I'VE heard nonsense, compared with which that would be as sensible as a dictionary!' (c) Lewis Carroll
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Давай так — изложи с подробностями свои веревки.
Я же уже объяснил, что вместо списка — дерево. Более подробно объяснить можно только если углублятся в детали какой-то конкретной реализации.
PD>Ничего не надо, только путь в дереве. Вот предположим он состоит из 20 фрагментов. Изменения касаются фрагментов с 5 по 7, остальные (1-4 и 8-20) без изменений. Что будет представлять собой новый путь ?
Не понял вопроса. Вы просите меня объяснить, как с помощью дерева можно организовать набор элементов, изменение которого не требует полного копирования для организации версионности? Вообще-то это надо бы знать.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>1. Выдачу этих строк в исходном порядке PD>2. Выдачу строк, отсортированых по любому из первых трех полей. (SELECT * ORDER BY FIELD1) PD>3. Выдачу любого набора полей в любом порядке из строк, отсортированных по любому из первых трех полей (SELECT FIELD2,FIELD5 ORDER BY FIELD1) PD>4. Выдачу аналогично п.3, но только для тех строк, у которых поле сортировки равно чему-то (SELECT FIELD2,FIELD5 ORDER BY FIELD1 WHERE FIELD1="ABCD")
PD>Для п.2-4 сортировка в момент запроса не допускается. Данные должны быть готовы для выдачи в этот момент без какой бы то ни было модификации.
поле должно присутствовать в памяти ТОЛЬКО ОДИН РАЗ. Хоть явно, хоть неявно. На вспомогательные структуры, так и быть, еще 50-70 Мб дам.
PD>Писать программу не прошу, само собой, но расскажи, как будешь хранить данные.
строим для них дерево по 2 указателя на каждый элемент 20 + 20 + 20 = 60
проекции строятся просто.
проверку с where делаем делением пополам. PD>Задачка несложная, не сомневаюсь, что ты решение предложишь. Просто сравним потом с моим.
А вот мое решение. на J
load 'csv'
data =. loadcsv 'c:\temp\2.csv'
sortby =. 4 : '(/: y {"1 x) { x'
.NB пример использования
.NB неотсортированные данные
data
┌──────────┬──────────┬──────────┬──────────┐
│nraxikrsma│nzptizmpib│ysufpwcisk│uglnldenrn│
├──────────┼──────────┼──────────┼──────────┤
│yjqxwfysjs│zvlnuucnjw│nadkmzxjhp│avkwjiqsqv│
├──────────┼──────────┼──────────┼──────────┤
│rmyonuvzub│owqpsumsxb│letdgrhzfy│shcvutxgib│
├──────────┼──────────┼──────────┼──────────┤
│kvebusxbmn│awrmmxwejf│femxmsyhdr│aswmkciktq│
├──────────┼──────────┼──────────┼──────────┤
│pxbwuihpoa│dpdorgepqa│rajatewzya│aexcdzuldz│
└──────────┴──────────┴──────────┴──────────┘
.NB сортируем по первой колонке
data sortby 0
┌──────────┬──────────┬──────────┬──────────┐
│kvebusxbmn│awrmmxwejf│femxmsyhdr│aswmkciktq│
├──────────┼──────────┼──────────┼──────────┤
│nraxikrsma│nzptizmpib│ysufpwcisk│uglnldenrn│
├──────────┼──────────┼──────────┼──────────┤
│pxbwuihpoa│dpdorgepqa│rajatewzya│aexcdzuldz│
├──────────┼──────────┼──────────┼──────────┤
│rmyonuvzub│owqpsumsxb│letdgrhzfy│shcvutxgib│
├──────────┼──────────┼──────────┼──────────┤
│yjqxwfysjs│zvlnuucnjw│nadkmzxjhp│avkwjiqsqv│
└──────────┴──────────┴──────────┴──────────┘
.NB сортируем по второй колонке
data sortby 1
┌──────────┬──────────┬──────────┬──────────┐
│kvebusxbmn│awrmmxwejf│femxmsyhdr│aswmkciktq│
├──────────┼──────────┼──────────┼──────────┤
│pxbwuihpoa│dpdorgepqa│rajatewzya│aexcdzuldz│
├──────────┼──────────┼──────────┼──────────┤
│nraxikrsma│nzptizmpib│ysufpwcisk│uglnldenrn│
├──────────┼──────────┼──────────┼──────────┤
│rmyonuvzub│owqpsumsxb│letdgrhzfy│shcvutxgib│
├──────────┼──────────┼──────────┼──────────┤
│yjqxwfysjs│zvlnuucnjw│nadkmzxjhp│avkwjiqsqv│
└──────────┴──────────┴──────────┴──────────┘
.NB сортируем по второй колонке , выбирая только первую и третью колонки
0 2 {"1 (data sortby 1)
┌──────────┬──────────┐
│kvebusxbmn│femxmsyhdr│
├──────────┼──────────┤
│pxbwuihpoa│rajatewzya│
├──────────┼──────────┤
│nraxikrsma│ysufpwcisk│
├──────────┼──────────┤
│rmyonuvzub│letdgrhzfy│
├──────────┼──────────┤
│yjqxwfysjs│nadkmzxjhp│
└──────────┴──────────┘
проверку на равенство не добавлял, но могу уверить, что это выльется еще в одну функцию которая будет фильтровать данные до сортировки.
Да, с первого раза выглядит страшно.
Да, жрет память.
Но позволяет комбинировать выборки как угодно без дополнительных телодвижений.
Позволяет транспонировать, отражать и вообще что угодно делать с матрицами не затрачивая никаких усилий.
Сортировка работает одинаково для строк и не для строк.
Для строк можно указать (легко) порядок сортировки. Хошь AaBbCc..., хошь ABCabc, или любые другие варианты.
А еще ходят слухи, что оно умеет раскидывать задачи на несколько ядер. Но тут не проверял, врать не буду.
Потрачено на реализацию полчаса, из которых 25 минут искал документацию к функциям, потому что давно не пользовался джеем. При регулярном использовании вообще плевая задача.
Есть еще альтернаривные варианты. Залить данные в БД, благо многие умеют считывать csv файлики, и получить хоть черта в ступе.
А можно csv открыть в Экселе. Кардинально да, но если задача одноразовая, пуркуа бы и не па ?
Я вообще к чему. Алгоритмы это хорошо. Это полезно, их должны знать. Но для развития имхо необходимо знать как можно больше различных подходов. чтобы решать задачу наиболее оптимальным для каждого случая способом.
Premature optimization is the root of all evil. (c)
Re[53]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Klapaucius, Вы писали:
PD>>Вполне согласен. Но asciiz меня здесь спасли. В сущности, твое решение ничем от моего не отличается. Поэтому я специально в пятницу не торопился выкладывать свое, ждал, что ты сделаешь один шаг, дойдешь до ASCIIZ, и мне останется только поздравить тебя с решением . Но тебе признать формат ASCIIZ религия не позволяет
K>Отличается принципиально. Я занимаюсь парсингом CSV один раз, а вы, фактически, парсите поток байтов, разделенных, извините за каламбур, разделителями каждый раз при чтении строки таблицы, хранящейся в памяти.
Да, но я решил задачу, а ты нет — твое решение не удовлетворяет условиям.
Здравствуйте, Klapaucius, Вы писали:
PD>>Ничего не надо, только путь в дереве. Вот предположим он состоит из 20 фрагментов. Изменения касаются фрагментов с 5 по 7, остальные (1-4 и 8-20) без изменений. Что будет представлять собой новый путь ?
K>Не понял вопроса. Вы просите меня объяснить, как с помощью дерева можно организовать набор элементов, изменение которого не требует полного копирования для организации версионности? Вообще-то это надо бы знать.
Слушай, может хватит меня поучать! Я тебе вполне конкретный вопрос задал. Если неясно — OK, изложу еще раз, немного упрощу
После некоторых действий для текста имеем 2 фрагмента
Фрагмент 1 показывает на кусок abcdefgh
Фрагмент 2 показывает на кусок stuvxyz
Добавляем новый фрагмент "123" между у u и v
Приведи , какие фрагменты получатся и как они выглядят.
K>Ну, вот поясняющая схема на языке dot.
Извини, но сначала следовало бы спросить, знаю ли я dot. Я его не знаю, так что это не ответ.
With best regards
Pavel Dvorkin
Re[43]: Зачем нужны циклы если есть рекурсивные функции
Кстати. Ты писал, что твои веревки дают копирование log(N) элементов. А в моем решении (с графом) копируется не более 2 элементов. Хоть при вставке, хоть при удалении. Да и зачем больше — путь в графе есть фактически список, а чтобы из этого списка получить новый список (новый путь в графе) путем однократного изменения , больше чем 2 элемента старого пути копировать незачем. Один слева, другой справа. Ну и еще новый элемент создать , если добавляем. Так что решение O(1).
With best regards
Pavel Dvorkin
Re[44]: Зачем нужны циклы если есть рекурсивные функции
PD>Я что-то не понял. Строк примерно 5 миллионов. Для каждой строки (кортежа) 4 интовых индекса
PD>5млн * 4 индекса * 4 байта_на_int = 80 Мб.
индекс имеется ввиду позиция элемента при сортировке по i-тому столбцу, а не индекс в смысле БД
пример
i i1 i2 i3 c1 c2 c3
0 1 2 1 b c b
1 2 0 3 c a d
2 3 3 0 d d a
3 0 1 2 a b c
где i — положение кортежей в неотсортированном виде,
i1,i2,i3 — положение кортежей в выборке, отсортированной по соотвествуем столбцу
c1,c2,c3 — данные соответственно
то есть, при сортировке строк по c1 мы должны быстро вывести строки в сдедующем порядке
сначала ту строку, где i1 ==0, потом ту, где i1 == 2, i1==3, i1 ==4
Но без дерева сложность такого бегания будет n^2
поэтому мы строим деревья для i1,i2,i3
Деревья нам позволят быстро вывести результат отсортированный по колонке, а также обеспечить двоичный поииск для сортировки с сравнением
Вроде в память в кладываемся.
Re[45]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Mirrorer, Вы писали:
M>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Я что-то не понял. Строк примерно 5 миллионов. Для каждой строки (кортежа) 4 интовых индекса
PD>>5млн * 4 индекса * 4 байта_на_int = 80 Мб.
M>индекс имеется ввиду позиция элемента при сортировке по i-тому столбцу, а не индекс в смысле БД
Да хоть в каком смысле, но sizeof его дай. Если его тип int — 4 байта вынь да положь. Если не int — тогда что ?
M>пример
<skipped>
Сначала с размером индекса давай разберемся.
With best regards
Pavel Dvorkin
Re[46]: Зачем нужны циклы если есть рекурсивные функции
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Да хоть в каком смысле, но sizeof его дай. Если его тип int — 4 байта вынь да положь. Если не int — тогда что ?
А в модифицированной мной задаче в этом решении практически ничего не надо менять. Оно работает и для текста, не поделенного на строки, и для текста из строк. Единственное, что надо изменить —
Вместо
Добавляемый фрагмент — в Б. Без длины и разделителей.
читать
Добавляемый фрагмент — в Б. Как он есть, включая имеющиеся в нем нулевые символы в конце строк. Без длины.
Вот и все. Разбиение на строки будет автоматически поддерживаться корректным образом при любой вставке или удалении.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, VladD2, Вы писали:
VD>>Я как-то уже думал на эту тему и пришел к выводу, что в языке можно было бы избавиться от лишней абстракции. Поля можно было бы переставлять как свойства с двумя публичными эксесорами. Это упростило бы язык и сделало бы более легким использование рефлексии (поля попросту можно было бы игнорировать во многих случаях).
PD>Я бы проще это сформулировал. ИМХО реализация дефолтных свойств как она есть в C# сделана не с той стороны. Вместо того, чтобы делать свойства с теневым полем, надо было сделать поля с автоматическим созданием свойства. Есть, к примеру, поле string name — автоматом создается свойство string Name с простейшей реализацией. Не нравится — напиши его сам. Ну и для полносты картины атрибут [Nonpropertable] запрещающий это либо для всего класса, либо для конкретного поля.
Нечто подобное сделано в языке Fan — http://fandev.org/doc/docLang/Fields.html
Можно писать по-всякому:
class Thing
{
Int justField := 0
Int overridedAccessors := 0
{
get { echo("get id"); return *overridedAccessors }
set { echo("set id"); *overridedAccessors = val }
}
virtual Int virtualField := 0
Int protectedSetter := 0 { protected set }
protected Int oneMore := 0
{
private set
get { return doSomething(*oneMore) } //getter will have protected visibility (field declaration)
}
}
Здравствуйте, AndrewVK, Вы писали:
AVK>А там можно заодно и делегаты приговорить.
Не, делегаты вещь очень полезная. Это ж по сути single-method interfaces, только вариантные и более мощные (duck typing). Надо правда добавить currying и приведение делегатов с одной сигнатурой. Ещё where T : delegate иногда не хватает.
