Двойно свързан списък срещу масив в текстови редактори

Започнах експериментален редактор на код, използвайки ncurses. Използвам двойно свързан списък за съхраняване/разбор/отпечатване на текста. Въпреки че съм далеч в изпълнението, не съм решил съвсем дали използването на двойно свързан списък е най-добрата идея или не (за разлика от използването на масиви).

Имайте предвид, че когато имам предвид масиви, имам предвид масив от знаци на ред - не един линеен масив.

Ето как претеглих плюсовете и минусите:

Двойно свързани списъци:

  • По-бързо вмъкване на знаци и редове
  • По-бързо сгъване на кода

Масиви:

  • Използвайте по-малко памет
  • Много по-бърз анализ
  • По-бързо печатане Имах ли право да използвам свързани списъци? Или те са по-добър начин да направите това?

Забележка:

Масивите се отпечатват по-бързо, защото трябва да има само едно извикване на printw, което отпечатва цял ред. За разлика от извикването на printw за символ.


c text-processing
person tay10r    schedule 19.06.2013    source източник
comment
Това може да е полезно: en.wikipedia.org/wiki/Rope_%28computer_science%29   -  person Blender    schedule 19.06.2013
comment
Сигурни ли сте, че масивите са по-бързи за печат? Мисля, че ще имат еднаква скорост за това. Освен това, ако използвате масиви, всички символи трябва да имат еднаква дължина, където свързаният списък позволява смесени дължини (странно е, когато „i“ заема толкова място, колкото „W“)   -  person David says Reinstate Monica    schedule 19.06.2013
comment
@Blender Благодаря, това е полезно.   -  person tay10r    schedule 19.06.2013
comment
@Dgrin91, да. Масивите (низовете) са по-бързи за отпечатване, защото трябва да извиквате printw само веднъж на ред - вместо да го извиквате за всеки символ (в lllist). Освен това масивите също могат да променят размера си и не е необходимо да имат подобни размери. Не съм съвсем сигурен какво имаш предвид с това.   -  person tay10r    schedule 19.06.2013
comment
Защо не използвате (двойно свързан) списък от низове, където всеки елемент в списъка е ред, така че можете да извиквате printw() веднъж на ред, както при масивите. Освен това драстично ще намалите изискването за съхранение; на 64-битова машина, двойно свързан списък от единични знаци вероятно ще използва 24 байта на знак, което е доста голямо натоварване.   -  person Jonathan Leffler    schedule 19.06.2013
comment
@JonathanLeffler, всъщност току-що започнах да правя това. Изглежда като доста приличен компромис (имам предчувствие, че това е, което nano използва). Вероятно ще изтрия този въпрос, защото мисля, че това е моето решение, с което ще работя. Също така, лоша идея ли е да използвате realloc при всяко вмъкване/премахване?   -  person tay10r    schedule 19.06.2013
comment
Вероятно бих проектирал възлите на списъка по линията на struct Line { struct Line *next; struct Line *prev; char *line; size_t line_len; size_t line_max; };, като line_len записва текущата дължина на реда, а line_max записва разпределеното пространство. Не бих извикал realloc(), когато знак беше изтрит; Вероятно не бих го направил, освен ако няма някакво доста голямо (256 байта?) несъответствие между действителния и максималния размер. [...продължение...]   -  person Jonathan Leffler    schedule 19.06.2013
comment
[...продължение...] За вмъквания бих преразпределил само когато вече нямаше място (когато line_len == line_max, но внимавайте да не е по-едно) и бих разпределил на стъпки от най-малко 16 знака (тъй като това вероятно е минималното количество, което malloc() et al действително разпределят така или иначе, плюс когато потребителят вмъква един знак, той често вмъква няколко). Така че, вие искате да избегнете промени за всеки символ в разпределението на паметта (извиквания към realloc()), без да се страхувате да преразпределите, когато е необходимо.   -  person Jonathan Leffler    schedule 19.06.2013
comment
@JonathanLeffler благодаря, ще започна да разпределям по 16 байта наведнъж   -  person tay10r    schedule 19.06.2013

Отговори (1)


arrow_upward
1
arrow_downward

Прехвърляне на коментари в отговор, тъй като никой друг не се включва.

Защо не използвате (двойно свързан) списък от низове, където всеки елемент в списъка е ред, така че можете да извиквате printw() веднъж на ред, както при масивите? Освен това драстично ще намалите изискването за съхранение; на 64-битова машина, двойно свързан списък от единични знаци вероятно ще използва 24 байта на знак, което е доста голямо натоварване.

Всъщност току-що започнах да го правя. Изглежда като доста приличен компромис (имам предчувствие, че това е, което нано използва). Вероятно ще изтрия този въпрос, защото мисля, че това е моето решение, с което ще работя. Също така, лоша идея ли е да използвате realloc() при всяко вмъкване/премахване?

Вероятно бих проектирал възлите на списъка по следния начин:

struct Line
{
    struct Line *next;
    struct Line *prev;
    char        *line;
    size_t       line_len;
    size_t       line_max;
};

като line_len записва текущата дължина на реда, а line_max записва разпределеното пространство.

Не бих извикал realloc(), когато символ е бил изтрит; Вероятно не бих го направил, освен ако няма някакво доста голямо (256 байта?) несъответствие между действителния и максималния размер.

За вмъквания щях да преразпределя само когато вече нямаше място (когато line_len == line_max, но внимавайте с един по един) и щях да разпределя на стъпки от поне 16 знака (защото това вероятно е минималното количество, което malloc() и др. всъщност разпределете така или иначе, плюс когато потребителят вмъкне един знак, той често вмъква няколко). Така че, вие искате да избегнете промени за всеки символ в разпределението на паметта (извиквания до realloc()), без да се страхувате да преразпределите, когато е необходимо.

person Jonathan Leffler    schedule 19.06.2013
comment
Благодаря. Какво ще стане, ако се пренеса към cpp и използвам std::string? Това ще използва ли много повече памет? Обмислям го само защото вмъкването и премахването на низ вече е направено с класа string. Освен това може лесно да преоразмери низа в n-byte блока. - person tay10r; 19.06.2013