Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let's assume for simplicity that only letters a-z appear in your texts.</p> <p>Initialize a list A with values a[i] = i for i = 1 to N (you will figure out yourself how big N should be).</p> <p>Perform (simulate) all your operations on A. After this analyze A to find required operations:</p> <p>Fist find required delete operations by finding missing numbers in A (they will form groups of consecutive values, one group stands for one delete operation). </p> <p>After this you can find required insert operations by finding sequences of consecutive letters (one sequence is one insert operation).</p> <p>In your example:</p> <p>init A:</p> <p>1 2 3 4 5 6 7 8 9 10</p> <p>Step 1 (+:2:ab):</p> <p>1 a b 2 3 4 5 6 7 8 9 10</p> <p>Step2 (+:1:cde):</p> <p>c d e 1 a b 2 3 4 5 6 7 8 9 10</p> <p>Step3 (-:4:1):</p> <p>c d e a b 2 3 4 5 6 7 8 9 10</p> <p>Now we search for missing numbers to find deletes. In our example only one number (namely number 1) is missing, so only 1 delete is required, so we have one delete operation: -:1:1 (In general there may be more numbers missing, every sequence of missing numbers is one delete operation. For example if 1, 2, 3, 5, 6, 10 are all missing numbers, then there are 3 delete operations: -:1:3, -:2:2, -:5:1. Remember that after every delete operation all indexes are decreased, you have to store total sum of former delete operations to calculate the index of current delete operation.)</p> <p>Now we search for character sequences to find insert operations. In our example there is only one sequence: cdeab at index 1, so we have one insert operation: +:1:cdeab</p> <p>Hope this is clear enough.</p>
    singulars
    1. This table or related slice is empty.
    1. POOptimize a list of text additions and deletions
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USwitzar
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COAnother very different approach, thank you! But it's not fast enough when actions are executed on very different positions, e.g. `+ 100000 a` and `- 2 1` —this can be done in O(1), while your solution needs 100000 characters to loop through three times...
      singulars
      1. PO
      1. USHarmen
    2. COwhat is complexity of your solution? can you give more complicated example of how it works? maybe: with more than one resulting insertion and deletion...
      singulars
      1. PO
      1. USWildWezyr
    3. CO@Harmen I only stated that to solve the problem it is best to perform operations and then read the result. I named data structure a List just for convinience of the argument, but I never defined it's implementation (LinkedList? TreeList? Custom implementation that pretends a[i]=i for uninitialized indexes?). But you didn't state how big is original text, how many input operation there is and what should be optimized, so I'm excused ;)
      singulars
      1. PO
      1. USwitzar
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload