<jupyter_start><jupyter_text>RMinimum : Runtime This file is for testing the runtime of the algorithm and each of the phases.<jupyter_code>import math
import random
import queue<jupyter_output><empty_output><jupyter_text>Runtime : RMinimum<jupyter_code># User input
n = 2**8
k = 2**2+0.2

# Automatic
X = [i for i in range(n)]

# ==================================================================
def rminimum(X, k, cnt = [], rec = 0):

    # Generate empty cnt list if its not a recursive call
    if cnt == []:
        cnt = [0 for _ in range(max(X) + 1)]

    # Convert parameters if needed
    k = int(k)
    n = len(X)

    # Base case |X| = 3
    if len(X) == 3:
        if X[0] < X[1]:
            cnt[X[0]] += 2
            cnt[X[1]] += 1
            cnt[X[2]] += 1

            if X[0] < X[2]:
                mini = X[0]
            else:
                mini = X[2]
        else:
            cnt[X[0]] += 1
            cnt[X[1]] += 2
            cnt[X[2]] += 1

            if X[1] < X[2]:
                mini = X[1]
            else:
                mini = X[2]
        return mini, cnt, rec

    # Run phases
    W, L, cnt = phase1(X, cnt)
    M, cnt = phase2(L, k, cnt)
    Wnew, cnt = phase3(W, k, M, cnt)
    mini, cnt, rec = phase4(Wnew, k, n, cnt, rec)

    return mini, cnt, rec

# --------------------------------------------------
#   Phase 1
def phase1(X, cnt):

    # Init W, L
    W = [0 for _ in range(len(X) // 2)]
    L = [0 for _ in range(len(X) // 2)]

    # Random pairs
    random.shuffle(X)
    for i in range(len(X) // 2):
        if X[2 * i] > X[2 * i + 1]:
            W[i] = X[2 * i + 1]
            L[i] = X[2 * i]
        else:
            W[i] = X[2 * i]
            L[i] = X[2 * i + 1]
        cnt[X[2 * i + 1]] += 1
        cnt[X[2 * i]] += 1

    return W, L, cnt

# --------------------------------------------------
#   Phase 2
def phase2(L, k, cnt):

    # Generate subsets
    random.shuffle(L)
    subsets = [L[i * k:(i + 1) * k] for i in range((len(L) + k - 1) // k)]

    # Init M
    M = [0 for _ in range(len(subsets))]

    # Perfectly balanced tournament tree using a Queue
    for i in range(len(subsets)):
        q = queue.Queue()

        for ele in subsets[i]:
            q.put(ele)

        while q.qsize() > 1:
            a = q.get()
            b = q.get()

            if a < b:
                q.put(a)
            else:
                q.put(b)
            cnt[a] += 1
            cnt[b] += 1
        M[i] = q.get()

    return M, cnt

# --------------------------------------------------
#   Phase 3
def phase3(W, k, M, cnt):

    # Generate subsets
    random.shuffle(W)
    W_i = [W[i * k:(i + 1) * k] for i in range((len(W) + k - 1) // k)]
    W_i_filt = [0 for _ in range(len(W_i))]

    # Filter subsets
    for i in range(len(W_i_filt)):
        W_i_filt[i] = [elem for elem in W_i[i] if elem < M[i]]
        cnt[M[i]] += len(W_i[i])
        for elem in W_i[i]:
            cnt[elem] += 1

    # Merge subsets
    Wnew = [w for sublist in W_i_filt for w in sublist]

    return Wnew, cnt

# --------------------------------------------------
#   Phase 4
def phase4(Wnew, k, n0, cnt, rec):
    
    # Recursive call check
    if len(Wnew) <= math.log(n0, 2) ** 2:
        q = queue.Queue()

        for ele in Wnew:
            q.put(ele)
        while q.qsize() > 1:
            a = q.get()
            b = q.get()

            if a < b:
                q.put(a)
            else:
                q.put(b)

            cnt[a] += 1
            cnt[b] += 1
        mini = q.get()
        return mini, cnt, rec

    else:
        rec += 1
        return rminimum(Wnew, k, cnt, rec)

# ==================================================
# Runtime
% timeit rminimum(X, k)<jupyter_output>4.54 ms ± 16.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)<jupyter_text>Runtime : Phase 1<jupyter_code># User input
n = 2**8

# Automatic
X = [i for i in range(n)]
cnt = [0 for _ in range(n)]

# ==================================================
def phase1(lst, cnt):
    
    random.shuffle(lst)

    W = [0 for _ in range(len(lst) // 2)]
    L = [0 for _ in range(len(lst) // 2)]

    for i in range(len(lst) // 2):
        if lst[2 * i] > lst[2 * i + 1]:
            W[i] = lst[2 * i + 1]
            L[i] = lst[2 * i]
        else:
            W[i] = lst[2 * i]
            L[i] = lst[2 * i + 1]
        cnt[lst[2 * i + 1]] += 1
        cnt[lst[2 * i]] += 1

    return W, L, cnt

# ==================================================
# Runtime
% timeit phase1(X, cnt)<jupyter_output>427 µs ± 3.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)<jupyter_text>Runtime : Phase 2<jupyter_code># User input
n = 2**8
k = 2**2

# Automatic
L = [i for i in range(n)]
cnt = [0 for _ in range(n)]

# ==================================================
def phase2(L, k, cnt):

    random.shuffle(L)
    
    subsets = [L[i * k:(i + 1) * k] for i in range((len(L) + k - 1) // k)]
    M = [0 for _ in range(len(subsets))]

    for i in range(len(subsets)):
        q = queue.Queue()

        for ele in subsets[i]:
            q.put(ele)

        while q.qsize() > 1:
            a = q.get()
            b = q.get()

            if a < b:
                q.put(a)
            else:
                q.put(b)
            cnt[a] += 1
            cnt[b] += 1
        M[i] = q.get()

    return M, subsets, cnt

# ==================================================
# Runtime
% timeit phase2(L, k, cnt)<jupyter_output>4.97 ms ± 27 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)<jupyter_text>Runtime : Phase 3<jupyter_code># User input
n = 2**8
k = 2**4

# Automatic
# W = [0, ..., 3/4 * n - 1, 3/4 * n + n/k, ..., n + n/k ]
# M = [3/4 * n, ..., 3/4 * n + n/k - 1]
W = [i for i in range(int(n + math.ceil(n / k)))]
M = [i for i in range(int(3 / 4 * n), int(3 / 4 * n + math.ceil(n / k)))]
for m in M:
    if m in W:
        W.remove(m)
cnt = [0 for _ in range(int(n + math.ceil(n / k)))]

# ==================================================
def phase3(W, k, M, cnt):
    random.shuffle(W)
    subsets = [W[i * k:(i + 1) * k] for i in range((len(W) + k - 1) // k)]
    subsets_filtered = [0 for _ in range(len(subsets))]

    for i in range(len(subsets_filtered)):
        subsets_filtered[i] = [elem for elem in subsets[i] if elem < M[i]]
        cnt[M[i]] += len(subsets[i])
        for elem in subsets[i]:
            cnt[elem] += 1

    Wnew = [item for sublist in subsets_filtered for item in sublist]
    
    return subsets, subsets_filtered, Wnew, cnt

# ==================================================
# Runtime
% timeit phase3(W, k, M, cnt)<jupyter_output>391 µs ± 3.67 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)<jupyter_text>Runtime : Phase 4<jupyter_code># User input
n = 2**10
n0 = 2**32

# Automatic
Wnew = [i for i in range(n)]
cnt = [0 for _ in range(n)]

# ==================================================
def phase4(Wnew, n0, cnt):

    if len(Wnew) <= math.log(n0, 2)**2:
        q = queue.Queue()

        for ele in Wnew:
            q.put(ele)
        while q.qsize() > 1:
            a = q.get()
            b = q.get()

            if a < b:
                q.put(a)
            else:
                q.put(b)

            cnt[a] += 1
            cnt[b] += 1
        mini = q.get()
        
        return mini, cnt
    
    else:
        return False, cnt

# ==================================================
# Runtime
% timeit phase4(Wnew, n0, cnt)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.23812700106723586, 'fraction_numerical': 0.027614727854855924, 'mean_word_length': 1.6622869318181819, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '132397', 'license': 'MIT', 'n_tokens_mistral': 2910, 'n_tokens_neox': 2709, 'n_words': 806, 'path': 'jupyter/jupyter_runtime.ipynb', 'repo_name': 'jfklorenz/Python-RMinimum', 'size': '7496'}