自组织数字序列并对其进行大量运算-最佳数据结构 [英] Self-organising sequence of numbers with big amount of operations on it - best data structure
问题描述
我需要帮助我选择适合自己的锻炼的正确数据结构。
I need help with choosing right data structure to my exercise.
对于输入，我得到了应该执行的操作数（ t ），然后在该索引的自然数序列之间用空格分隔。
例如：
For input I have been given number of operations that should be executed(t) and after that indexed sequence of natural numbers seperated with a space. So for example:
3 1 2 3
3 1 2 3
这意味着将在序列{1,2,3}上执行3个操作。
This means that there will be 3 operations executed on sequence {1,2,3}.
还定义了一个指针，该指针显示当前位置。我应该对该序列执行的操作是：
There is also defined a pointer, which shows current position. Operations on that sequence that I should implement are:
-
R ->删除元素 c 在索引 PTR + 1 上，并将 PTR 向前移动 c 次
R -> removing element c on index PTR+1 and moving PTR forward c times
X ->插入在元素 c 之后，该元素位于索引 PTR 上（因此插入 PTR + 1 ），值为 c-1 的元素，并且当然会将 PTR 向前移动 c 次。
X -> inserting right after element c, which is on index PTR (so inserting on PTR+1), element with value of c-1 and of course moving PTR forward c times.
我的工作是在执行操作 R 和 X 之后找到结束序列t 次，因此如果其元素为 even ，则执行 R ，否则执行 X 。在开始处 PTR 显示第一个元素（如果存在），并且应该全部循环。
My job is to find ending sequence after performing operations R and X t times so that if its element is even then do the R, else do the X. At the start PTR shows first element(if exists) and it should be all in cycle.
对于在发布开始处的给定示例， 输出应为：
For given example at the start of post the output should be:
0 0 3 1
0 0 3 1
我知道这听起来可能令人困惑，所以让我向您展示这应该如何逐步进行。
I know that it might sound confusing, so let me show you how this should work step by step.
t = 1
开始顺序：
1 2 3
Starting sequence: 1 2 3
实际位置： PTR -> 1
操作： X ， c = 1
结束顺序：
1 0 2 3
Ending sequence: 1 0 2 3
结束位置：PTR-> 0
Ending position: PTR -> 0
t = 2
开始顺序：
1 0 2 3
Starting sequence: 1 0 2 3
实际位置： PTR -> 0
Actual position: PTR -> 0
操作： R ，
结尾序列：
1 0 3
Ending sequence: 1 0 3
结尾位置：PTR-> 1
Ending position: PTR -> 1
t = 3
开始顺序：
1 0 3
Starting sequence: 1 0 3
实际位置： PTR -> 1
操作： X ， c = 1
结束顺序：
1 0 0 3
Ending sequence: 1 0 0 3
结束位置：PTR-> 0
Ending position: PTR -> 0
解决方案是 PTR 中正确方向的序列。因此输出应为：0 0 3 1
The solution is a sequence from PTR in right direction. So output should be: 0 0 3 1
至于限制：
-
C序列的起始长度最多10 ^ 7
starting length of C sequence up to 10^7
t 操作的数量最多10 ^ 7
number of t operations up to 10^7
将 PTR 右移最多10 ^ 9次
moving PTR to right up to 10^9 times
我已经创建了基于循环链表的算法。可以，但是对于某些测试来说太慢了。如果有人可以帮助我找到最佳的数据结构，我将不胜感激。
I have created my algorithm, which is based on circular linked list. Works, but it's too slow for some tests. I'd be more than grateful if someone could help me in finding the best data structure.
我的老师也暗示我应该使用二进制列表，但老实说，我在互联网上找不到任何有关此结构的信息！也许有人也知道这件事，然后告诉我在哪里可以找到有关它的信息？我会很感激。
I've got also a hint from my teacher that I should use binary list, but to be honest I didn't find anything about this structure on the internet! Maybe also someone knows this thing and show me where can I search for information about it? I'd apreciate any help.
推荐答案
使用圆形双向链表。它具有O（1）插入和删除。 （也许这就是您的讲师所说的二进制列表。）
Use a circular doubly linked list. It has O(1) insert and remove. (Perhaps this is what your instructor meant by "binary list.")
有趣的事实：您可以使用 XOR技巧与在此处编码。由于更好的缓存行为，较低的内存利用率将意味着较大列表的速度更快。在XOR链接列表上还有一个 SO Q& A ，列出了它的一些缺点。
Fun fact: you can reduce the memory utilization of a doubly linked list with an XOR trick with code here. Lower memory utilization will mean better speed for large lists due to better cache behavior. There's also a SO Q&A on XOR linked lists, which itemizes some of its drawbacks.
这篇关于自组织数字序列并对其进行大量运算-最佳数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
