Read a paper: Ropes-- an alternative to Strings

  Рет қаралды 7,110

Vivek Haldar

Vivek Haldar

Күн бұрын

Boehm, H. J.; Atkinson, R.; Plass, M. F. Ropes: an alternative to strings. Software Practice and Experience. 1995 December; 25 (12): 1315-1330.
Link to paper: www.cs.rit.edu/usr/local/pub/...
vivekhaldar.com
/ vivekhaldar

Пікірлер: 7
@monad_tcp
@monad_tcp 6 ай бұрын
(from the title only) At first I though this was about Physics, but then I remembered I'm actually graduated in Compsci
@julianyumanji1159
@julianyumanji1159 Жыл бұрын
Thank u and please continue this series
@anon_y_mousse
@anon_y_mousse 5 ай бұрын
I read that paper and it seems to suggest that the method I use for allocation is actually faster than using a rope. I use a geometric allocation scheme and I retain the length of the string. As far as the example of reading in a file by lines, it's a shame I didn't read this paper sooner because it's not too dissimilar from the method I came up with independently where I create a sparse array where it's just a series of partially filled buffers in a balanced tree referenced by their indices. Unless I'm misunderstanding what they're saying where it sounds like they're saying each node in a rope would be sized specifically for whatever data it stores, while I used the same size for each node and allowed for unfilled space before and after each string piece. I used a tag to denote a partial line which actually allowed me to size the buffers in relation to the screen width in characters so that I could very easily wrap lines. It was a lazy method because words would be clipped in half in a lot of cases, but it was really fast when it came to edits. It wouldn't be too difficult to wrap by words, it would just require a slight adjustment to the buffer filling code, but maybe I should continue developing it.
@VivekHaldar
@VivekHaldar 5 ай бұрын
That sounds neat. You should do a proper comparison with ropes and write it up! The Xi editor used ropes and was written in rust if you're looking for a reference implementation. xi-editor.io/docs/rope_science_00.html
@delian66
@delian66 3 ай бұрын
Thank you. I like your channel a lot.
@loogabarooga2812
@loogabarooga2812 5 ай бұрын
Why mention that an issue with char array strings is immutability and then not go into how ropes approach that at all lmao I remember as a college project trying to figure out how to make a text editor and I did end up using a rope. I still don't know how immutability comes into it, and I'm pretty sure I read this specific paper
@delian66
@delian66 3 ай бұрын
@OmerTairi-cf1jxunfortunately I think that people that use `lmao` unironically can not help you or anyone else.
Rope Datastructure
21:06
mjölnir
Рет қаралды 13 М.
Fixing RAG with GraphRAG
15:04
Vivek Haldar
Рет қаралды 695
КАРМАНЧИК 2 СЕЗОН 5 СЕРИЯ
27:21
Inter Production
Рет қаралды 605 М.
1❤️
00:20
すしらーめん《りく》
Рет қаралды 33 МЛН
1 класс vs 11 класс  (игрушка)
00:30
БЕРТ
Рет қаралды 1,1 МЛН
Cloud Security & SOC Analyst 8:15PM 05/June/2024 Day 2
44:25
Read a paper: A database-oriented operating system
10:03
Vivek Haldar
Рет қаралды 740
LLMs as compilers
7:12
Vivek Haldar
Рет қаралды 940
WHY IS THE HEAP SO SLOW?
17:53
Core Dumped
Рет қаралды 193 М.
The Algorithm Behind Spell Checkers
13:02
b001
Рет қаралды 395 М.
Understanding B-Trees: The Data Structure Behind Modern Databases
12:39
I made a Compression Algorithm for Heightmap Terrain
16:00
mohsen zare
Рет қаралды 65 М.
So You Think You Know Git - FOSDEM 2024
47:00
GitButler
Рет қаралды 971 М.
Main filter..
0:15
CikoYt
Рет қаралды 905 М.