stack.py

   1 #!/usr/bin/env python
   2
   3 # Any copyright is dedicated to the Public Domain.
   4 # https://creativecommons.org/publicdomain/zero/1.0/
   5
   6 # Written by Francois Fleuret <francois@fleuret.org>
   7
   8 import torch, torchvision
   9
  10 ######################################################################
  11
  12 # CODE_OP=[0 for push, 1 for pop] + 2 * n_stack
  13 # CODE_VAL=val + 2 * nb_stacks
  14
  15
  16 def generate(nb, seq_len, nb_stacks, nb_values):
  17     stack = torch.empty(nb, nb_stacks, seq_len, dtype=torch.int64)
  18     stack_pointers = torch.zeros(nb, nb_stacks, dtype=torch.int64)
  19     k = torch.arange(nb)
  20     result = torch.empty(nb, 2 * seq_len, dtype=torch.int64)
  21
  22     for t in range(seq_len):
  23         op = torch.randint(2, (nb,))
  24         st = torch.randint(nb_stacks, (nb,))
  25         op = op * (stack_pointers[k, st] > 0)
  26         val_push = torch.randint(nb_values, (nb,))
  27         # top_val[n,s]=stack[n,stack_pointers[n,s]]
  28         top_values = stack[
  29             k,
  30             st,
  31             (stack_pointers[k, st] - 1).clamp(min=0),
  32         ]
  33         stack[
  34             k[:, None].expand_as(stack_pointers),
  35             st[:, None].expand_as(stack_pointers),
  36             stack_pointers,
  37         ] = val_push[:, None].expand_as(stack_pointers)
  38         stack_pointers[k[op == 0], st[op == 0]] += 1
  39         stack_pointers[k[op == 1], st[op == 1]] -= 1
  40         result[:, 2 * t] = st * 2 + op
  41         result[:, 2 * t + 1] = (op * top_values + (1 - op) * val_push) + 2 * nb_stacks
  42
  43     return result
  44
  45
  46 def seq_to_str(seq):
  47     assert seq.size(0) % 2 == 0
  48     s = ""
  49     for t in range(0, seq.size(0), 2):
  50         op = seq[t]
  51         op = f"POP_{op//2}" if op % 2 == 1 else f"PUSH_{op//2}"
  52         val = seq[t + 1] - 2 * nb_stacks
  53         if t > 0:
  54             s += " "
  55         s += f"{op} {val}"
  56     return s
  57
  58
  59 ######################################################################
  60
  61 if __name__ == "__main__":
  62     nb, seq_len, nb_stacks, nb_values = 3, 10, 1, 5
  63     result = generate(nb=nb, seq_len=seq_len, nb_stacks=nb_stacks, nb_values=nb_values)
  64     for n in range(result.size(0)):
  65         print(seq_to_str(result[n]))