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

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和read_end将始终受r1和r2的端点的界限。

此示例范围很小，但是在我的应用程序中，它们可能会大于10亿，因此我正在寻找一个时间和记忆效率的解决方案。

我考虑将其发布到编程难题＆amp;代码高尔夫。看来这应该是一个简单明了的过程……但是它被我击败了。

n.b。我并不是在这里真正从文件中读取，因此我无法使用涉及Python文件对象的解决方案。我只是将文件用作方便的类比。

Answer 1

应将间隔分开为子间隔。让我在此示例上解释一下：

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

subintervals的边界都是所有开始，结数，即：0,2,3,4,5。可以忽略read_start和" read_end"之前的数字，因此5算出。我们现在有0,2,3,4。不太明显的是，位于range1内的range2边界也可以忽略，因此3也出现了。边界是 0,2,4，这意味着亚智能为 0-2和 2-4。

其余的很容易。我们从具有所需范围的数据源中阅读 - 尊重优先级。范围不是从零开始，因此必须考虑偏移。

def prioritized_read(range1, range2, read_start, read_end):
    d1, r1 = range1
    d2, r2 = range2
    bset = set((read_start, read_end))
    for b in r1: 
        if read_start < b < read_end:
            bset.add(b)
    for b in r2: 
        if not r1[0] < b < r1[1] and read_start < b < read_end:
            bset.add(b)
    boundaries = sorted(bset)
    output = []
    for i in range(len(boundaries) - 1): 
        start, end = boundaries[i], boundaries[i+1]
        if r1[0] <= start < r1[1]:
            # read from #1
            output.append(d1[start-r1[0]:end-r1[0]])
        elif r2[0] <= start < r2[1]: 
            # read from #2
            output.append(d2[start-r2[0]:end-r2[0]])
        else:
            raise ValueError("no data source for {}:{}".format(start, end))
    return "".join(output)

Answer 2

类似的东西为您提供了所需的输出：

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开头，并且范围不是不相交的。如果范围很大