如何有效地覆盖两个字符串，其中一个字符串优先于另一个字符串？

Question

我有两个字符串作为文件范围的缓冲区。我想从这个“文件”中读取，以便优先从第一个字符串读取字节，而不是从第二个字符串读取字节，第二个字符串有重叠。在

在下面的示例中，r1和r2分别表示文件的范围，它们由字符串以及起始偏移量和结束偏移量组成。我已经格式化了这些示例，以便更清楚地显示字符串在文件中的位置。在

def prioritized_read(range1, range2, read_start, read_end):
    # This is the bit I don't know how to write

r1 = ("ABCDEF", (0,6))
r2 = ( "DEF",   (1,4))
assert prioritized_read(r1, r2, 0, 6) == "ABCDEF"

r1 = ("ABC",    (0,3))
r2 = ( "DEF",   (1,4))
assert prioritized_read(r1, r2, 1, 4) == "BCF"

r1 = (  "ABC",  (2,5))
r2 = ("DEF",    (0,3))
assert prioritized_read(r1, r2, 0, 4) == "DEAB"

r1 = ( "A",     (1,2))
r2 = ("DEF",    (0,3))
assert prioritized_read(r1, r2, 0, 3) == "DAF"

r1 = ("ABC",    (0,3))
r2 = (   "DEF", (3,6))
assert prioritized_read(r1, r2, 3, 6) == "DEF"

read_start和{}将始终由r1和{}的端点为界。在

这里的示例范围很小，但在我的应用程序中，它们可能超过10亿个，所以我正在寻找一个节省时间和内存的解决方案。在

我考虑过把这个贴到Programming Puzzles & Code Golf。看起来这应该是一个简单明了的过程。。。但它打败了我。在

注意：我并不是真正从文件中读取，所以我不能使用涉及Python文件对象的解决方案。我只是用文件作为一个方便的类比。在

Answer 1

这样可以获得所需的输出：

def prioritized_read(r1, r2, start, end):
    s = [''] * max(r1[1][1], r2[1][1])
    s[r2[1][0]:r2[1][1]] = r2[0]
    s[r1[1][0]:r1[1][1]] = r1[0]

    return ''.join(s[start:end])

这假设其中一个范围总是以0开头，并且这些范围不是不相交的。如果范围很大，这可能不会节省内存

Answer 2

您可以创建一个所需长度的数组，然后在正确的位置复制range2和{}的字符。在

所有测试都通过了：（编辑：用切片分配替换了难看的for循环。）

def _override_chars(array, string, indices, read_start, read_end):
    substring_start = max(0, read_start - indices[0])
    substring_end = read_end - indices[0]
    substring = string[substring_start:substring_end]

    insertion_start = max(0, indices[0] - read_start)
    insertion_end = insertion_start + len(substring)
    array[insertion_start:insertion_end] = substring


def prioritized_read(range1, range2, read_start, read_end):
    a = [None] * (read_end - read_start)
    _override_chars(a, *range2, read_start, read_end)
    _override_chars(a, *range1, read_start, read_end)
    return ''.join(a)

---

编辑： 另一个解决方案是建立一个发电机。它的内存效率更高，因为不需要同时在内存中保存数组和最后一个字符串。在

^{pr2}$

Answer 3

区间应划分为子区间。让我用这个例子来解释一下：

r1 = (  "ABC",  (2,5))
r2 = ("DEF",    (0,3))
assert prioritized_read(r1, r2, 0, 4) == "DEAB"

子区间的边界都是起始号和结束号，即：0,2,3,4,5。read_开始之前和read_结束之前的数字可以忽略，因此5是out。我们现在有0,2,3,4。不太明显的是，位于range1内的range2边界也可以被忽略，所以3也是不存在的。边界是0,2,4，这意味着子区间是0-2和{}。在

剩下的很容易。我们从数据源中读取数据，该数据源具有所需的范围-考虑优先级。范围不是从零开始的，所以必须考虑偏移量。在

^{pr2}$