Автор Тема: Архитектура текстового редактора  (Прочитано 25526 раз)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Архитектура текстового редактора
« Ответ #15 : Март 07, 2012, 09:26:31 am »
Если не ставить перед моделью задач помимо обеспечения эффективной работы ядра текстового редактора, то да.  :) Эффективное произвольное позиционирование и/или задача извлечения символа по индексу нужны только при программной работе с текстом. А манипуляции текстом в редакторе в основном как "на рельсах" происходят. Двусвязного списка достаточно.
Если говорить про произвольное позиционирование по номеру строки в редакторе (Ctrl+"G"), то тут не грех и линейным поиском...

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Архитектура текстового редактора
« Ответ #16 : Март 07, 2012, 06:23:46 pm »

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Архитектура текстового редактора
« Ответ #17 : Март 12, 2012, 09:11:59 am »
Всё что я раньше сказал про двухсвязный список отправляется в сад ибо уже не актуально...  :)

Сейчас измерил на современном компьютере время вставки элемента в массив -- оно ничтожно. Поэтому для представления текста на современном компьютере уже не нужны никакие там сложные структуры, а достаточно взять просто массив символов. Вставляешь символ -- тупо сдвигаешь все последующие символы на одну позицию и не паришься на счёт того, что это якобы медленно. Уже не медленно!!!

И так. Номер буквы - 4 байта, номер атрибутов - 4 байта, итого 8 байтов на символ. Измеряем сколько времени займёт вставка символа в позицию 0 если длина текста 1'000'000 восьмибайтовых символов.

      public void Insert (int position, long value)
      {
         this.length++;
         // this.CheckCapacity();
         for (int n = position; n < this.length; n++)
         {
            long t = this.array[n];
            this.array[n] = value;
            value = t;
         }
      }

Получаем всего лишь 962 микросекунды на Core i7 2600K с памятью DD3 1600 MHz.

Не забываем, что в 2014 появится DDR4 которая раза в два-три быстрее чем DDR3.


valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Архитектура текстового редактора
« Ответ #18 : Март 12, 2012, 09:15:50 am »
Получаем всего лишь 962 микросекунды на Core i7 2600K с памятью DD3 1600 MHz.

Не забываем, что в 2014 появится DDR4 которая раза в два-три быстрее чем DDR3.
Интересней были бы тесты на, скажем, intel atom. Ибо в качестве печатной машинки (текстового редактора) обычно таки именно подобные дивайсы используют. Ну и на arm'e.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Архитектура текстового редактора
« Ответ #19 : Март 12, 2012, 09:23:34 am »
Сейчас измерил на современном компьютере время вставки элемента в массив -- оно ничтожно. Поэтому для представления текста на современном компьютере уже не нужны никакие там сложные структуры, а достаточно взять просто массив символов. Вставляешь символ -- тупо сдвигаешь все последующие символы на одну позицию и не паришься на счёт того, что это якобы медленно. Уже не медленно!!!
Если уж пример на C#, то там для этого есть более эффективный метод - Array.Copy(...)

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Архитектура текстового редактора
« Ответ #20 : Март 12, 2012, 10:52:14 am »
С System.Array.Copy получилось 535 микросекунд.

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Архитектура текстового редактора
« Ответ #21 : Март 12, 2012, 11:03:47 am »
У меня нет intel atom, зато дома есть Pentium 4. Потом измерю на нём. Но даже если будет в десять раз медленнее, так ведь текст в 1'000'000 символов тоже ого-го. Обычно тексты сильно короче.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Архитектура текстового редактора
« Ответ #22 : Март 12, 2012, 11:12:16 am »
У меня нет intel atom, зато дома есть Pentium 4. Потом измерю на нём. Но даже если будет в десять раз медленнее, так ведь текст в 1'000'000 символов тоже ого-го. Обычно тексты сильно короче.
Это ж всего лишь мегабайтный текст. А логи например бывают и по 100 мегабайт. Или скажем какой-нибудь дамп базы. Понятно что по уму с ними надо работать не через текстовый редактор, но иногда под рукой просто больше ничего нет.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Vartovyj

  • Full Member
  • ***
  • Сообщений: 197
    • Просмотр профиля
Re: Архитектура текстового редактора
« Ответ #23 : Март 12, 2012, 11:30:04 am »
Бывают и многогигабайтные текстовые файлы до 200млн строк (сам с такими работаю).

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Архитектура текстового редактора
« Ответ #24 : Март 12, 2012, 12:34:09 pm »
Если файл на столько большой, то и нечего загружать его целиком в редактор. Используем скользящее окно в миллион букв.

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Архитектура текстового редактора
« Ответ #25 : Март 12, 2012, 01:45:53 pm »
Да... решение в лоб  :D
Я ради опыта конечно веревки скорее всего буду использовать. Однако простой двусвязный список тоже привлекателен. Я тут на днях обнаружил что в книжке "Прожект Оберон" есть описание архитектуры тамошней текстовой подсистемы. В основе то же что в ЧК. Но разработчики ЧК столько там насвистоперделили, что разглядеть виртовскую элегантность уже трудно.  :)
Надо оригинальный Оберон поглядеть...

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Архитектура текстового редактора
« Ответ #26 : Март 12, 2012, 03:04:31 pm »
Интересней были бы тесты на, скажем, intel atom. Ибо в качестве печатной машинки (текстового редактора) обычно таки именно подобные дивайсы используют. Ну и на arm'e.
Если Fusion E450 катит, то кидайте свой тест сюда. Замеряем время. Только не забудьте сказать версию нета. Не уверен, что у меня оно вообще есть, а всё подряд ставить на комп тоже не особо хочется.

Valery Solovey

  • Hero Member
  • *****
  • Сообщений: 509
    • Просмотр профиля
Re: Архитектура текстового редактора
« Ответ #27 : Март 12, 2012, 03:12:09 pm »
Это ж всего лишь мегабайтный текст. А логи например бывают и по 100 мегабайт. Или скажем какой-нибудь дамп базы. Понятно что по уму с ними надо работать не через текстовый редактор, но иногда под рукой просто больше ничего нет.
Редактировать логи - это сильно : ). Разговор с заказчиком: "Я тут посмотрел свои логи {но мы-то знаем...} - никаких проблем. Или проблема не на нашей стороне".

Сто мегабайт - это сто массивов по 1 мегу.

А несколько гигов в ОЗУ загрузить... Я таки вас умоляю, не говорите мне, что собираетесь прочесть каждую строчку лога. А грепами лог вполне можно уменьшить до приемлемого размера.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Архитектура текстового редактора
« Ответ #28 : Март 12, 2012, 03:13:21 pm »
Всё что я раньше сказал про двухсвязный список отправляется в сад ибо уже не актуально...  :)

Стопудово :) Я вот когда в свою контору пришел был сначала удивлен использованию векторов там, где казалось бы "по всем правилам" должен был быть список (вставка в середину, удаление из середины). Однако на практике оно тупо быстрее  :)

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Архитектура текстового редактора
« Ответ #29 : Март 12, 2012, 03:40:12 pm »
Если Fusion E450 катит, то кидайте свой тест сюда. Замеряем время. Только не забудьте сказать версию нета.

namespace TestCopy
{
   public sealed class ArrayString
   {
      private long[] array;
      private int length;

      public ArrayString (int length)
      {
         this.length = length;
         this.array = new long[length + 10000];
         for (int k = 0; k < length; k++)
         {
            this.array[k] = k;
         }
      }

      public void Insert (int position, long value)
      {
         System.Array.Copy(this.array, position, this.array, position + 1, this.length);
         this.length++;
         this.array[position] = value;
      }
   }

   class Program
   {
      static void Main (string[] args)
      {
         ArrayString x = new ArrayString(1000000);
         const int K = 1000;
         System.DateTime t0 = System.DateTime.UtcNow;
         for (int k = 0; k < K; k++)
         {
            x.Insert(0, 42);
         }
         System.DateTime t1 = System.DateTime.UtcNow;
         double dt = 1000000 * (t1 - t0).TotalSeconds / K;
         System.Console.WriteLine("dt = {0} microseconds", dt);
         System.Console.ReadLine();
      }
   }
}

Во вложении проект и бинарь для .Net 3.5