Здравствуйте, gear nuke, Вы писали:

LVV>>Я тоже. Но EDX не изменяется автоматически при выполнении команды CALL, a ESP — изменяется.

GN>Intel Architecture Software Developer's Manual, Volume 1: Basic Architecture
GN>

...

GN>Используется оно когда захочет автор.
GN>

It is possible, in some cases, to temporarily reuse ESP as a general purpose register. Since the x86 architecture is so register-starved, adding an eighth register can eliminate the need to spill variables to memory and boost the speed of a critical inner loop. I've used this in a couple of places in VirtualDub when I really needed it, and some have asked if it is actually safe to do this. The answer is yes...

здесь
Это говорит о том, что В НЕКОТОРЫХ случаях мы можем использовать ESP как регистр общего назначения. Кто ж с этим спорит. А вот ОБРАТНОЕ — НЕВЕРНО. Мы НЕ МОЖЕМ использовать ни один регистр общего назначения в качестве ESP. Оговорюсь, можно попробовать ESI и EDI, поскольку они автоматом изменяются при некоторых операциях. Но засылку в стек адреса возврата придется моделировать.
GN>"Стек значений" от eax до нуля:
GN>

GN>f:  dec eax
GN>    jz @f
GN>    call f
GN>@@: retn
GN>

Ваш фрагмент только подтверждает особый статус ESP: он тут нигде не упомянут, а используется. Попробуйте в этой роли использовать EAX — не получится. И, кстати, в стеке нет никаких параметров — только адреса возврата.

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>>>Двумя словами — проход с барьером. Если хочешь пример аналога без битов — проход циклического списка с псевдоначалом (неким выбранным элементом, с которого стартуем и который содержит, скажем, NULL в поле данных).

GN>>>То что я называю маркером, имеет значение совпадающее с возможным для данных.

PD>>NULL — совершенно корректное значение для данных.

GN>Внутри С-строки?

Поля данных списка. Я же пример привел, см выше, и так понял, что ты о нем и говоришь.

PD>> Впрочем, если не нравится NULL — поставь указатель на некий статический объект и проверяй на равенство ему.

GN>Еще раз. В моем примере идёт последовательность битов. 1 и 0 — это валидные значения для данных. "Маркер" имеет значение 1. Помимо других проблем, нужно как-то уметь определить, что конкретный 1 — это именно маркер окончания, а не данные.

Ну знаешь ли, ты многого хочешь. Твой конкретный 1, который именно маркер, а не данные, есть в действительности однобитовый регистр под названием флаг С. А без него ты не сделаешь.

PD>>>>Другое дело, что это лишнее, проход и без этого "маркера" можно провести.

GN>>>Можно, но потребует дополнительных ресурсов.

PD>>Каких ?

GN>В 1м примере был использован счётчик битов.
GN>

    mov eax, [pixels]  
GN>    mov ecx, 32  
GN>@@: shr eax, 1  ; копируем очередной бит в Carry Flag
GN>    ;
GN>    ; тут что-то делаем с битом
GN>    ;
GN>    dec ecx  ; итерируем цикл
GN>    jnz @b
GN>

А во втором примере использован дополнительный бит (флаг С). Ты доказал, что здесь не обязательно иметь дополнительно 32 бита, а хватит одного.

PD>>cur = start->next; // начало с NULL пропустим
PD>>while(cur->data)
PD>> cur = cur->next;

GN>Одно из полей — лишнее. Осталось объедлинить data и next в одну ячейку памяти.

А чего тут объединять ? Они и так рядом в памяти лежат

PD>>>>Не так уж мало. И там и тут проход с барьером. Только ты (и я в варианте со списком) этот барьер заносишь явно, а для char* его занесли до нас.

GN>>>Аналогом могла бы служить последовательность только из байтов 0 и 1.

PD>>Ну где я тебе возьму такие байты ?

GN>

char s[] = '\0\1\1\0\1\0\1\0\1\0";

GN>Очевидно strlen не посчитает длину.

Посчитает Ответ — 0. И правильный ответ.

Кстати, ты с milti-sz форматом знаком ?

abc'\0'def'\0'xyz'\0' и ноль в конце, то есть фактически 2 нуля в конце.

Очень симпатичный формат. Им многие пользуются, даже не зная этого

PD>> И чем тебя остальные 254 не устраивают ?

GN>Они впринципе устраивают. Не устраивает невозможность наличия 0 в середине.

Если не секрет — зачем тебе в текстовых строках нужен нуль в середине ?

Здравствуйте, LaptevVV, Вы писали:

LVV>Это говорит о том, что В НЕКОТОРЫХ случаях мы можем использовать ESP как регистр общего назначения. Кто ж с этим спорит. А вот ОБРАТНОЕ — НЕВЕРНО.

А я обратное и не утверждаю. Как раз говорю, что нечего загонять себя в рамки.

LVV> Мы НЕ МОЖЕМ использовать ни один регистр общего назначения в качестве ESP. Оговорюсь, можно попробовать ESI и EDI, поскольку они автоматом изменяются при некоторых операциях. Но засылку в стек адреса возврата придется моделировать.

Моделировать придётся разве что получение EIP, поскольку это не GPR и напрямую недоступен.

GN>>"Стек значений" от eax до нуля:
GN>>

GN>>f:  dec eax
GN>>    jz @f
GN>>    call f
GN>>@@: retn
GN>>

LVV>Ваш фрагмент только подтверждает особый статус ESP: он тут нигде не упомянут, а используется.

Он упомянут в инструкциях call и retn. Позвольте мне воздержаться от дальнейшего цитирования мануала.

LVV> Попробуйте в этой роли использовать EAX — не получится.

Попробую ECX, что бы не менять способ передачи параметра.

    mov ecx, esp
    dec ch
    ;
f:  dec eax
    jz @f
    sub ecx, 4
    mov [ecx], @f
    jmp f
@@: add ecx, 4
    jmp [ecx-4]

LVV>И, кстати, в стеке нет никаких параметров — только адреса возврата.

Разумеется.

Только при этом придется моделировать стек в виде сохранения предыдущих значений переменных

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>У меня телепатических способностей нет.

Для того, чтобы понять из слов "одного узла дерева" что речь идет о деревьях не нужно быть телепатом, так что второй раз переспрашивать нужно разве только для того, чтобы увести разговор от темы.
Для того, чтобы понять, что речь с самого начала шла о деревьях также не нужно телепатии — нужны минимальные представления о структурах данных.

Разговоры о телепатии для меня интереса не представляют — мы говорим об эффективной реализации строк и я привел примеры структур данных, для которых типичные операции со строками алгоритмически более выгодны. Какой-нибудь ответ на это будет?

PD>Статистику в студию!

Интересует статистика — ее не сложно получить. Посчитать лоличество измерений длинны строки в достаточно объемном коде, который работает с ASCIIZ строками. Но уже второе ваше заявление

PD> В моей как раз наоборот было.

Указывает на то, что один случай для вас интереснее любой статистики.

PD>А где я говорил, что я вообще читаю эти строки с диска?

Ну ладно — времени получения блока по сети. Все, больше строкам взяться неоткуда. Но чтение блока откуда угодно существенно медленнее, чем инкремент счетчика блоков.

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>С объектником ясно, но все же не пойму, почему править PE заголовок можно только на асме, а на С нельзя. Что там такое в асме есть особенное ?

GN>Никто заголовки не правит, линкер добавляет информацию из объектника при сборке. Директива .SAFESEH В С такого нет. Там возможна только автоматическая регистрация __except блоков, а не произвольных функций.

Понятно. Но это не возможности С или асма, а скорее организация работы с MASM или VC

Здравствуйте, Pavel Dvorkin, Вы писали:

GN>>Еще раз. В моем примере идёт последовательность битов. 1 и 0 — это валидные значения для данных. "Маркер" имеет значение 1. Помимо других проблем, нужно как-то уметь определить, что конкретный 1 — это именно маркер окончания, а не данные.

PD>Ну знаешь ли, ты многого хочешь. Твой конкретный 1, который именно маркер, а не данные, есть в действительности однобитовый регистр под названием флаг С. А без него ты не сделаешь.

В действительности... (начинаю объяснять код) у меня один 33х битный регситр — аккумулятор с переносом. Необходимость 33х битов обусловлена необходимостью закодировать константу 32. Меньшую константу я сделаю и на С без флагов.

PD>А во втором примере использован дополнительный бит (флаг С). Ты доказал, что здесь не обязательно иметь дополнительно 32 бита, а хватит одного.

Я показал как закодировать константу 32 другой константой — размером регистра в битах.

PD>>>cur = start->next; // начало с NULL пропустим
PD>>>while(cur->data)
PD>>> cur = cur->next;

GN>>Одно из полей — лишнее. Осталось объедлинить data и next в одну ячейку памяти.

PD>А чего тут объединять ? Они и так рядом в памяти лежат

Лежа рядом в памяти, они занимают в 2 раза больший объём — дополнительные ресурсы, о которых я говорил.

PD>>>>>Не так уж мало. И там и тут проход с барьером. Только ты (и я в варианте со списком) этот барьер заносишь явно, а для char* его занесли до нас.

GN>>>>Аналогом могла бы служить последовательность только из байтов 0 и 1.

PD>>>Ну где я тебе возьму такие байты ?

GN>>

char s[] = '\0\1\1\0\1\0\1\0\1\0";

GN>>Очевидно strlen не посчитает длину.

PD>Посчитает Ответ — 0. И правильный ответ.

Для strlen правильный. Но остальные данные не будут обработаны при таком подходе.

PD>Кстати, ты с milti-sz форматом знаком ?

Да конечно, это уже бюлиже к теме

PD>Если не секрет — зачем тебе в текстовых строках нужен нуль в середине ?

Мне не нужен, я показываю что задача со strlen имеет мало общего.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Понятно. Но это не возможности С или асма, а скорее организация работы с MASM или VC

Да, я про то и говорю — практически все остальное делается в рамках С

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>У меня телепатических способностей нет.

K>Для того, чтобы понять из слов "одного узла дерева" что речь идет о деревьях не нужно быть телепатом, так что второй раз переспрашивать нужно разве только для того, чтобы увести разговор от темы.
K>Для того, чтобы понять, что речь с самого начала шла о деревьях также не нужно телепатии — нужны минимальные представления о структурах данных.

Цитирую первое твое сообщение


>Вопрос во-первых, в том, сколько динамической памяти выделяется. Выделить подстроку можно, например, выделяя константное кол-во памяти, а не >линейное. И результат конкатенации строк длинной N и K можно получить выделяя константное или логарифмическое кол-во памяти, а не N+K.

Если из этой фразы можно уловить. что речь идет о каких-то деревьях с самого начала — тогда точно, я понять ничего не умею.

K>Разговоры о телепатии для меня интереса не представляют — мы говорим об эффективной реализации строк и я привел примеры структур данных, для которых типичные операции со строками алгоритмически более выгодны. Какой-нибудь ответ на это будет?

Будет, если внятно изложишь то, о чем речь идет. Если уж речь идет о деревьях, будь добр объяснить структуру дерева. Двоичное ? Нет ? trie ? Что там в узле, буквы ?

PD>>Статистику в студию!

K>Интересует статистика — ее не сложно получить.

Вот когда получишь — тогда и будем разговаривать.

>Посчитать лоличество измерений длинны строки в достаточно объемном коде, который работает с ASCIIZ строками.

И что ?

>Но уже второе ваше заявление

PD>> В моей как раз наоборот было.

K>Указывает на то, что один случай для вас интереснее любой статистики.

И это тоже, потому что мне в моей программе нужно , чтобы в ней было хорошо. Но статистику давай. С приведением кода. А то одна только болтовня и ничем не доказанные утверждения.


PD>>А где я говорил, что я вообще читаю эти строки с диска?

K>Ну ладно — времени получения блока по сети. Все, больше строкам взяться неоткуда.

Да ну ? Так-таки и неоткуда ? Я уж не говорю про ввод с клавиатуры, хотя большинство строк именно такой генезис имеют. Я уж не говорю про OCR, из которого в компьютеры пришли остальные строки прежде чем их записали на диск или отправили в сеть.
Но открою тебе секрет — есть еще возможность из одних строк делать другие в самой программе

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, Pavel Dvorkin, Вы писали:

PD>>Понятно. Но это не возможности С или асма, а скорее организация работы с MASM или VC

GN>Да, я про то и говорю — практически все остальное делается в рамках С

Ну вроде все выяснили. С тобой интересно дискутировать

Здравствуйте, gear nuke, Вы писали:

GN>Здравствуйте, Pavel Dvorkin, Вы писали:

GN>В действительности... (начинаю объяснять код) у меня один 33х битный регситр — аккумулятор с переносом. Необходимость 33х битов обусловлена необходимостью закодировать константу 32. Меньшую константу я сделаю и на С без флагов.

Ну да. Кстати, вполне можешь в 64-битный код это превратить. Ты просто играешь на специфике команды RCR.

GN>Я показал как закодировать константу 32 другой константой — размером регистра в битах.

Ну можно и так сказать. Но что это меняет ? То. что у тебя ее явно нет, а вместо этого ты ее неявно определяешь, используя специфику RCR ?

GN>>>Одно из полей — лишнее. Осталось объедлинить data и next в одну ячейку памяти.

PD>>А чего тут объединять ? Они и так рядом в памяти лежат

GN>Лежа рядом в памяти, они занимают в 2 раза больший объём — дополнительные ресурсы, о которых я говорил.

Я что-то не понял ? Ты что., хочешь 2 указателя в 4 байта засунуть ?

GN>>>

char s[] = '\0\1\1\0\1\0\1\0\1\0";

GN>>>Очевидно strlen не посчитает длину.

PD>>Посчитает Ответ — 0. И правильный ответ.

GN>Для strlen правильный. Но остальные данные не будут обработаны при таком подходе.

А их для нее нет. . Она так сделана. By design.

PD>>Кстати, ты с milti-sz форматом знаком ?

GN>Да конечно, это уже бюлиже к теме

PD>>Если не секрет — зачем тебе в текстовых строках нужен нуль в середине ?

GN>Мне не нужен, я показываю что задача со strlen имеет мало общего.

Ладно, давай заканчивать

Здравствуйте, Pavel Dvorkin, Вы писали:

>>Вопрос во-первых, в том, сколько динамической памяти выделяется. Выделить подстроку можно, например, выделяя константное кол-во памяти, а не >линейное. И результат конкатенации строк длинной N и K можно получить выделяя константное или логарифмическое кол-во памяти, а не N+K.
PD>Если из этой фразы можно уловить. что речь идет о каких-то деревьях с самого начала — тогда точно, я понять ничего не умею.

Программист изучает структуры данных для того, чтобы по желаемой асимптотике подобрать соответствующую структуру данных. В данном случае деревья должны приходить на ум одними из первых.

PD>Будет, если внятно изложишь то, о чем речь идет. Если уж речь идет о деревьях, будь добр объяснить структуру дерева.

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

PD>Двоичное ? Нет ? trie ? Что там в узле, буквы ?

Речь идет о веревках. Это линейные буферы и дерево конкатенации. Или, например, о пальчиковых деревьях. Но во втором случае, понятно, оверхэд на размещение одного символа вам не понравится.

PD>И что ?

И то. Это и будет статистика. Причем вы сами можете выбрать примкер кода из области которая вам интересна.

K>>Указывает на то, что один случай для вас интереснее любой статистики.
PD>И это тоже, потому что мне в моей программе нужно , чтобы в ней было хорошо.

Какая то перевернутая логика. Обычно решают, что нужно — исходя из того, что хорошо. Ну или соглашаются на то, что остается — но что уж тут хорошего? А назначать хорошим то, что нужно — это, простите, гегельянство какое-то!

PD>Но статистику давай. С приведением кода. А то одна только болтовня и ничем не доказанные утверждения.

Про доказательство — смешно.

K>>Ну ладно — времени получения блока по сети. Все, больше строкам взяться неоткуда.
PD>Да ну ? Так-таки и неоткуда ? Я уж не говорю про ввод с клавиатуры, хотя большинство строк именно такой генезис имеют.

Замечание потрясающей ценности. Вот уж на фоне набивания текста вручную инкремент счетчика просто ошеломляюще затратен. О чем речь!

PD>Я уж не говорю про OCR, из которого в компьютеры пришли остальные строки прежде чем их записали на диск или отправили в сеть.

О да, распознавание текста существенно замедлится однократным вычислением длинны строки. Это ж даже сравнивать невозможно — какое-то распознавание — тьфу! Мелочи. А однократное вычисление длинны — это огого!

Еще раз. Чтение блока откуда угодно существенно медленнее, чем инкремент счетчика блоков.

PD>Но открою тебе секрет — есть еще возможность из одних строк делать другие в самой программе

Правда?!? Открою секрет вам — существует арифметика. Она позволяет вычислять из длин операндов длинну результата.

Здравствуйте, Pavel Dvorkin, Вы писали:

GN>>Я показал как закодировать константу 32 другой константой — размером регистра в битах.

PD>Ну можно и так сказать. Но что это меняет ? То. что у тебя ее явно нет, а вместо этого ты ее неявно определяешь, используя специфику RCR ?

Специфика ни при чем:

void f (uint32_t bitmask)
{
  if ( bitmask & 0x80000000 ) dosmth();
  bitmask = bitmask + bitmask + 1; // добавляем маркер к последовательности
  do
  {
    if ( bitmask & 0x80000000 ) dosmth();
    bitmask = bitmask + bitmask;
  }
  while ( bitmask != (1 << 31) ) // ловим маркер. последовательность будет пуста
}

Есть последовательность битов, анонимной функции определённой после do передаётся остаток последовательности, она проверяет, что он не пустой.

GN>>>>Одно из полей — лишнее. Осталось объедлинить data и next в одну ячейку памяти.

PD>>>А чего тут объединять ? Они и так рядом в памяти лежат

GN>>Лежа рядом в памяти, они занимают в 2 раза больший объём — дополнительные ресурсы, о которых я говорил.

PD>Я что-то не понял ? Ты что., хочешь 2 указателя в 4 байта засунуть ?

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

PD>Ладно, давай заканчивать

PD>

Здравствуйте, Klapaucius, Вы писали:

Здравствуйте, Klapaucius, Вы писали:

Ладно. Давай закончим пустые рассуждения. Вот тебе конкретная задача. Я ее не выдумал, это (с небольшими модификациями) то, что мне реально пришлось делать.

Дан файл в формате CSV. 10 полей на строчку, есть пустые поля. Поля не длинные, обычно 5-10 символов. Количество строк известно, порядка 5 миллионов. Размер файла 200 Мб, известен точно.

Делай что хочешь, но должен обеспечить

1. Выдачу этих строк в исходном порядке
2. Выдачу строк, отсортированых по любому из первых трех полей. (SELECT * ORDER BY FIELD1)
3. Выдачу любого набора полей в любом порядке из строк, отсортированных по любому из первых трех полей (SELECT FIELD2,FIELD5 ORDER BY FIELD1)
4. Выдачу аналогично п.3, но только для тех строк, у которых поле сортировки равно чему-то (SELECT FIELD2,FIELD5 ORDER BY FIELD1 WHERE FIELD1="ABCD")

Для п.2-4 сортировка в момент запроса не допускается. Данные должны быть готовы для выдачи в этот момент без какой бы то ни было модификации.

Вся информация должна быть в ОП, чтение из файла можно провести только один раз.
Можешь завести нужные вспомогательные структуры, массивы и т.п, но копировать строки не разрешается. Иными словами, каждая исходное текстовое поле должно присутствовать в памяти ТОЛЬКО ОДИН РАЗ. Хоть явно, хоть неявно. На вспомогательные структуры, так и быть, еще 50-70 Мб дам.

Писать программу не прошу, само собой, но расскажи, как будешь хранить данные.

Задачка несложная, не сомневаюсь, что ты решение предложишь. Просто сравним потом с моим.

Здравствуйте, Pavel Dvorkin, Вы писали:

Это задача построения базы данных только для чтения. К строкам имеет весьма опосредованное отношение.
Мы читаем байты из потока, разбивая на блоки по разделителям и организуем в таблицу. После этого создаем вспомогательные структуры в которых храним порядок для первых трех столбцов и структуру для ускорения фильтрации. Результат запроса у нас — набор блоков, которые мы отдаем в поток. Все. Ни одной операции со строками нет. Т.е. задача совершенно нерелевантна обсуждаемым вопросам.

Теперь моя задача.

Есть текст (не разделен на строки одинаковой длины), который можно редактировать. Т.е. вставлять, удалять, добавлать в начало, в конец символ/блок символов. Должен поддерживаться "бесконечный" (пока есть свободная память) undo/redo на каждое изменение + дерево версий. Также, желательно, иметь возможность сравнивать версии. Понятно, что для хранения версии следует занимать разумный объем, сопоставимый с объемом изменений сделанных в этой версии, а не хранить весь текст.

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

Здравствуйте, Klapaucius, Вы писали:

K>Здравствуйте, Pavel Dvorkin, Вы писали:

K>Это задача построения базы данных только для чтения. К строкам имеет весьма опосредованное отношение.

Имеет, имеет. База там или не база — а вот тебе файл из строк, их надо и выдавать.


K>Мы читаем байты из потока, разбивая на блоки по разделителям и организуем в таблицу

Пожалуйста, подробнее про эти таблицы. Сколько будет в них элементов и каков их размер в байтах ?

>После этого создаем вспомогательные структуры в которых храним порядок для первых трех столбцов и структуру для ускорения фильтрации.

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

>Результат запроса у нас — набор блоков, которые мы отдаем в поток.

Куда отдаем — не суть важно, а вот что это за блоки и каков их размер — пожалуйста, подробнее.

>Все. Ни одной операции со строками нет.

Изменения строк действительно нет. Это верно. Но из этого не следует, что нет работы с ними.

>Т.е. задача совершенно нерелевантна обсуждаемым вопросам.

Хоть релевантна, хоть нет, а размер вспомогательных данных оцени. И как будешь собственно символы строк — тоже. В виде строк (String C#, string STL...) или как ?


K>Теперь моя задача.

Жду сначала ответы для моей задачи.


K>Я, на самом деле, не понял, зачем вы поставили свою задачу. Надеюсь, что моя поможет вам переключиться с проблем, которые не связаны с операциями над строками, на проблемы, которые с этими операциями связаны.

Смотря что под операциями понимать

Да, забыл сказать. Исходные строки в ASCII. Но об этом можешь не беспокоиться. Будем считать, что в твоем распоряжении класс ASCIIString, ведет себя как обычный класс String, только хранит байты, а не двухбайтники.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Имеет, имеет. База там или не база — а вот тебе файл из строк, их надо и выдавать.

Не имеет. По-вашему, например, решение уравнения пьезопроводности тоже работа со строками, если мы читаем входные данные из текстового файла, ага?

K>>Мы читаем байты из потока, разбивая на блоки по разделителям и организуем в таблицу
PD>Пожалуйста, подробнее про эти таблицы. Сколько будет в них элементов

Сколько значений разделенных запятыми, столько и блоков.

PD>и каков их размер в байтах ?

Не имеет никакого значения.

>>После этого создаем вспомогательные структуры в которых храним порядок для первых трех столбцов и структуру для ускорения фильтрации.
PD>Тоже, пожалуйста, подробнее о том. что это за структуры и каков их размер.

Первые гне имеют совсем уже никакого отношения к работе со строками. Ну, например, списки номеров строк таблицы сортированные по соответствующему столбцу. Во втором случае это зависит от того, что требуется от фильтрации — точное соответсвие или сопоставление с образцом.

PD>а вот что это за блоки и каков их размер — пожалуйста, подробнее.
"читаем байты из потока, разбивая на блоки по разделителям"

>>Все. Ни одной операции со строками нет.
PD>Изменения строк действительно нет. Это верно.

На этом, в общем-то можно было и закончить.
Строки можно и не изменять. Я говорю о том, что нет операций над строками. Вернее есть, конкатенация, но она выполняется выходным потоком. Т.е. можно при решении этой задачи обойтись без строк (т.е. некоторого абстрактного типа данных, для которого есть операции конкатенации, вставки, удаления, выделения подстроки и т.д.) вообще.

PD>Но из этого не следует, что нет работы с ними.

К обсуждаемой теме это отношения не имеет.

>>Т.е. задача совершенно нерелевантна обсуждаемым вопросам.
PD>Хоть релевантна, хоть нет, а размер вспомогательных данных оцени. И как будешь собственно символы строк — тоже. В виде строк (String C#, string STL...) или как ?

Не релевантна и не обсуждается.

PD>Жду сначала ответы для моей задачи.

А, ну понятно, вы сейчас будете ждать, пока я подсчитаю все биты до последнего. Так дело не пойдет. Сейчас вы решаете мою задачу с той же степенью конкретизации, что и я вашу. А там видно будет. Биты считать не надо. Нужен асимптотический анализ сложности алгоритмов и расходов памяти.

PD>Смотря что под операциями понимать

Понимать следует:
конкатенацию,
выделение подстроки,
удаление подстроки,
вставку подстроки.

Что вообще говоря было перечислено в моей задаче.

Здравствуйте, Klapaucius, Вы писали:

K>Не имеет. По-вашему, например, решение уравнения пьезопроводности тоже работа со строками, если мы читаем входные данные из текстового файла, ага?

Если исходные данные читаем из текстовых строк и парсим их — да. Но это к делу не относится.

K>>>Мы читаем байты из потока, разбивая на блоки по разделителям и организуем в таблицу
PD>>Пожалуйста, подробнее про эти таблицы. Сколько будет в них элементов

K>Сколько значений разделенных запятыми, столько и блоков.

Отлично.

PD>Дан файл в формате CSV. 10 полей на строчку, есть пустые поля. Поля не длинные, обычно 5-10 символов. Количество строк известно, порядка 5 миллионов. Размер файла 200 Мб, известен точно.

5 миллионов строк. 10 полей на строку. 50 миллионов полей.

PD>>и каков их размер в байтах ?

K>Не имеет никакого значения.

Имеет. Потому что я написал в условии

PD>На вспомогательные структуры, так и быть, еще 50-70 Мб дам.


При таких условиях на каждый из этих блоков получается не более чем по 1, от силы 2 байта. А на блок надо хоть ссылку, хоть указатель оформить. А ее (его) размер 4 байта. А длину блока хранить будем ? Если в формате, как в string, то это еще 4 байта, итого 8. 8 байт на 50 миллионов полей — 400 Мб.

Понял теперь, куда я веду ?


K>На этом, в общем-то можно было и закончить.

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

PD>>Но из этого не следует, что нет работы с ними.

K>К обсуждаемой теме это отношения не имеет.

Ну-ну. Я-то ведь в свои 50-70 Мб уложусь.

K>А, ну понятно, вы сейчас будете ждать, пока я подсчитаю все биты до последнего.

Я их уже подсчитал, хоть и не до последнего. Кое-что еще добавится.

K>Ну, например, списки номеров строк таблицы сортированные по соответствующему столбцу.

Как эти списки делать будешь — не спрашиваю, а вот размер оценим.

Пусть 4 байта на элемент списка (что явно занижено, ну да ладно). Пусть только по первым 3 полям. А строк у нас 5 миллионов. Еще 20 Мб на каждую строку и каждый столбец. На 3 столбца — 60 Мб.

Итого 400 Мб + 60 Мб = 460 Мб




>Так дело не пойдет. Сейчас вы решаете мою задачу с той же степенью конкретизации, что и я вашу.

Пока что решения нет. У меня дополнительных 500 Мб не имеется. Меня за такое решение выгонят сразу.


>А там видно будет. Биты считать не надо. Нужен асимптотический анализ сложности алгоритмов и расходов памяти.

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


PD>>Смотря что под операциями понимать

K>Понимать следует:
K>конкатенацию,
K>выделение подстроки,
K>удаление подстроки,
K>вставку подстроки.

А парсинг уже не входит ? String.Split из класса String выкинуть ? А ведь я именно задачу на парсинг и представил.

FYI. У нас уже 17:30. В выходные я в Интернете не бываю. В понедельник у меня занятия с утра до вечера. Так что отвечу либо в понедельник, если урву время, либо во вторник. У тебя есть время подумать

Здравствуйте, Klapaucius, Вы писали:

K>А, ну понятно, вы сейчас будете ждать, пока я подсчитаю все биты до последнего.

Не, все намного смешнее. Он скажет, что у него нет времени на всякую ерунду. Мы это уже проходили.