5

Say we have big list of integer numbers, stored as comma-separated values in a macro or token register. Now we want to test in a loop for every integer n = 1, 2, ..., N if n occurs in the list of numbers. For small N and short lists traversing until a match is found is fine. As this is O(n2) behavior, traversing the whole list over and over again may slow down compilation for largers inputs notably.

What options are there for a more efficent way to test for integer membership?

Edit: As requested some more information:

The solution should work with pdflatex, so no Lua code. expl3 solutions are fine.

The big list of numbers can be assumed to be in ascending order for my use case. Even for a more general solution, where a non-sorted list is provided, we could apply \clist_sort:Nn to get a sorted input list.

My specific use case is to place markers in the document that are numbered by a counter on the first compilation run. At the end of the process a possibly big list of these marker counters (not all of them) is written to the .aux file and processed on the next run. At each marker location the list has to be tested if that specific element occurs in the list. In the worst case we'll have all elements in the list and have to traverse the list up to position i at marker number i, which gives an O(n2) behavior in the end.

Beside this specific use case I think the problem could be interesting for other problems as well.

  • 3
    Please indicate whether LuaLaTeX-based answers are acceptable to you. Please also provide a bit more information about the somewhat mysterious "big list[s] of integers". E.g., can the integers be assumed to be in (ascending or descending) order? – Mico Jul 4 '19 at 6:38
  • 1
    If you only want to test if an integer n=1,2,...N occurs in the list you only need to loop over the list and select all instances that are smaller than N+1. Why is this O(n^2)? Could you perhaps explain more precisely what you want, i.e. in which form you want the information? – user121799 Jul 4 '19 at 7:52
  • @Mico: See updated question please – siracusa Jul 4 '19 at 19:57
5

The classical approach here is to use a (tiny) font as an array, exploiting the fontdimens. For a single array we can do

\font\myintarray = cmr10 at 1sp %
\count255 = 0 %
\loop
  \advance\count255 by 1 %
  \fontdimen\count255 \myintarray = 0sp %
  \ifnum\count255 < 11 %
\repeat
\protected\def\setarray#1#2{%
  \fontdimen#1 \myintarray = #2sp %
}
\def\getarray#1{%
  \number\fontdimen#1 \myintarray
}
\setarray{5}{27}
\count255 = 255 %
\loop
  \advance\count255 by 1 %
  \getarray{\count255 } %
  \ifnum\count255 < 11 %
\repeat
\bye

with more arrays we need a little management (each one has to be a separate font). These structures are global but have constant access time (so a mapping will have linear time).


In expl3 this approach is abstracted as the intarray data type

\intarray_new:Nn \g_my_intarray { 100 }
\intarray_gset:Nnn \g_my_intarray { 5 } { 27 }
\intarray_item:Nn \g_my_intarray { 5 }

In terms of limitations, the key one is that the maximum value is one power lower than the usual TeX limit (2^{30} - 1 rather than 2^{31} - 1). There is, that I know of, no pre-determined limit on the number of fonts that can be loaded. However, the total number of fontdimens (that is, the number of items in the array) is limited: with standard settings, 4 million entries are allowed.

|improve this answer|||||
  • The documentation of l3intarray says that the access is in constant time, so this should be too, right? – Phelype Oleinik Jul 4 '19 at 17:57
  • @PhelypeOleinik Yes, that's rather the point ... we can directly access any element rather than having to iterate through – Joseph Wright Jul 4 '19 at 18:00
  • Thanks, I wasn't sure. I asked because at the end of the answer you say "linear time" :-) – Phelype Oleinik Jul 4 '19 at 18:02
4

UPDATE: It is maybe just me, but I cannot follow the argument that there is an O(n^2) cost. Of course, this may only be a misunderstanding since in your question n is used for various objects. Let us call the number of elements of the big integer list M, and its largest element n_max. Then I claim that you need "only" M+n_max steps. There is no quadratic dependence on the number of entries or the length of the list or anything. The following code addresses your updated problem: you have a possibly large list and want to have a membership test. This is achieved by \ProcessList{<list>}{<largest entry>}. The detailed implementation can certainly be improved (I am sure you can add more \expandafters and \ignorespaces and so on), but the point is that there is no quadratic dependence whatsoever.

\documentclass{article}
\newcounter{iloop}
\makeatletter
\newcommand{\ProcessList}[2]{\setcounter{iloop}{0}%
\loop%
\stepcounter{iloop}%
\edef\temp{\noexpand\xdef\csname member\roman{iloop}\endcsname{0}}%
\temp%
\ifnum\number\value{iloop}<\the\numexpr#2+1\repeat%
\@for\next:=#1\do{\edef\mynum{\romannumeral\next}%
\expandafter\xdef\csname member\mynum\endcsname{1}}}
\newcommand{\IsInList}[2]{%
\edef\temp{\noexpand\xdef\noexpand#2{\csname member\romannumeral#1\endcsname}}%
\temp}
\makeatother
\begin{document}
% we assume that the list is known as well as its largest element
% they will become the arguments of \ProcessList
% (the largest element can also be found out automatically)
\ProcessList{1,2,3,4,6,9,10,14,19,21,22,25,30,33,%
35,38,39,40,42,44,49,50,59,60,62,63,64,%
66,67,70,71,80,82,83,85,88,89,94,95,96,%
97,99,103,106,107,109,112,116,117,119,121,%
123,126,128,132,133,134,138,139,140,141,%
143,147,148,150,153,155,157,163,165,168,%
170,176,177,178,180,184,186,190,197,202,%
207,208,209,219,220,224,234,235,238,239,%
242,244,247,249,251,259,262,265,267,268,%
270,275,280,283,285,287,288,289,292,300,%
301,303,307,311,313,314,315,318,319,323,%
324,325,326,327,331,337,346,352,354,356,%
361,362,363,366,367,368,369,372,375,377,%
378,382,383,384,388,391,393,394,395,398,%
399,400,402,404,405,407,408,409,412,417,%
421,423,426,434,439,440,443,445,446,448,%
456,461,466,467,468,470,472,477,478,479,%
481,482,483,485,489,493,494,496,500,502,%
505,509,512,514,518,522,527,528,530,531,%
533,535,536,541,545,548,551,553,554,556,%
557,560,562,564,565,566,570,571,572,575,%
577,587,593,600,601,604,605,607,610,611,%
613,614,619,621,622,623,625,632,633,634,%
635,636,637,639,645,648,651,656,661,665,%
666,669,674,677,678,679,680,682,683,684,%
685,687,689,690,693,698,700,703,704,708,%
710,713,714,718,719,729,730,733,737,738,%
741,744,745,746,753,760,761,762,765,770,%
772,775,780,782,783,784,789,790,792,801,%
803,804,806,809,810,814,815,818,822,823,%
824,827,829,833,836,837,838,840,841,843,%
844,847,849,853,854,855,859,864,870,871,%
873,874,876,881,882,885,887,889,890,891,%
892,893,895,900,901,903,908,910,911,913,%
915,917,919,920,922,925,927,928,931,932,%
933,934,935,936,938,942,943,945,951,956,%
959,963,964,966,971,972,974,978,989,993,%
995,997,998}{998}

test if 6 is in the list:\IsInList{6}{\mytest} \mytest

test if 7 is in the list:\IsInList{7}{\mytest} \mytest
\end{document}

enter image description here

OLD ANSWER: In order to select those are no larger than M you need only one loop over all M elements. This gives you a list of K elements, say. At this stage, the cost is M. If you want to find out if a given integer is in the big list, you also only need M steps.

In any case, these are some basic routines that do something along these lines. I strongly believe similar routines must exist somewhere but I couldn't find them.

\documentclass{article}
\newcounter{iloop}
\newif\ifmember
\newif\iflstart
\makeatletter% for \@for see e.g. https://tex.stackexchange.com/a/100684/121799
\newcommand{\MemberQ}[2]{\global\memberfalse%
\@for\next:=#1\do{\ifnum\next=#2\global\membertrue\fi}}
\newcommand{\Preselect}[3]{\edef\itest{\the\numexpr#2+1}%
\lstarttrue%
\@for\next:=#1\do{\ifnum\next<\itest%
\iflstart%
\xdef#3{\next}%
\global\lstartfalse%
\else%
\xdef#3{#3,\next}%
\fi%
\fi}}
\newcommand{\Hits}[3]{\edef#3{-1}%
\lstarttrue%
\setcounter{iloop}{-1}\loop%
\stepcounter{iloop}%
\MemberQ{{#1}}{\number\value{iloop}}%
\ifmember%
\iflstart%
\xdef#3{\number\value{iloop}}%
\global\lstartfalse%
\else%
\xdef#3{#3,\number\value{iloop}}%
\fi\fi%
\ifnum\number\value{iloop}<#2\repeat}
\makeatother
\begin{document}
\subsection*{Tests of MemberQ}
\MemberQ{1,2,3,4}{2}
\ifmember 2 is in list \fi

\MemberQ{1,2,3,4}{5}
\ifmember 2 is in list \fi

\subsection*{Select all members of list which are smaller than or equal to a certain number}
% random list generated by Mathematica
\edef\LstLong{638, 761, 899, 899, 315, 827, 954, 696, 102, 577, 
525, 279, 108, 983, 845, 530, 658, 896, 818, 342, 
515, 946, 62, 632, 495, 784, 218, 583, 624, 761, 
230, 176, 38, 801, 514, 643, 720, 991, 930, 219, 
115, 585, 527, 115, 837, 50, 955, 566, 579, 600, 
184, 987, 212, 941, 966, 63, 192, 973, 801, 322, 
571, 946, 786, 433, 586, 997, 903, 820, 672, 618, 
355, 338, 183, 384, 479, 341, 507, 849, 431, 292, 
470, 927, 93, 460, 518, 865, 257, 712, 351, 732, 
817, 839, 217, 951, 194, 222, 604, 292, 208, 220, 
197, 476, 973, 232, 250, 527, 972, 496, 751, 824, 
334, 342, 751, 484, 883, 526, 644, 424, 368, 410, 
530, 243, 600, 216, 661, 273, 412, 685, 724, 12, 
556, 587, 380, 43, 792, 827, 687, 568, 275, 608, 
893, 863, 825, 741, 831, 406, 855, 83, 279, 290, 
341, 7, 381, 256, 437, 292, 945, 474, 326, 970, 820, 
44, 539, 903, 640, 592, 285, 512, 594, 788, 677, 
197, 787, 927, 400, 239, 220, 342, 14, 902, 677, 
858, 481, 824, 925, 639, 677, 903, 287, 223, 271, 
997, 774, 602, 293, 766, 10, 416, 638, 311, 186, 
729, 613, 31, 930, 219, 357, 887, 88, 579, 985, 446, 
334, 910, 447, 321, 183, 862, 297, 641, 139, 980, 
199, 687, 374, 322, 22, 319, 991, 672, 788, 262, 
828, 389, 684, 178, 958, 492, 597, 803, 259, 386, 
800, 86, 936, 712, 494, 447, 254, 932, 78, 789, 121, 
897, 120, 819, 935, 307, 246, 96, 16, 639, 549, 85, 
867, 509, 960, 690, 301, 348, 440, 792, 117, 157, 
567, 184, 912, 244, 686, 843, 112, 927, 328, 801, 
178, 720, 385, 380, 399, 377, 287, 76, 574, 291, 
731, 430, 670, 466, 758, 104, 825, 23, 502, 821, 
979, 753, 28, 970, 855, 958, 20, 999, 184, 598, 668, 
877, 736, 174, 850, 715, 131, 289, 786, 55, 36, 785, 
129, 851, 411, 677, 493, 913, 405, 630, 695, 582, 
555, 806, 65, 775, 448, 774, 905, 925, 353, 356, 
106, 884, 178, 176, 182, 114, 258, 112, 924, 923, 
853, 959, 300, 652, 729, 141, 14, 493, 94, 281, 668, 
173, 834, 855, 839, 665, 361, 168, 808, 34, 179, 
736, 139, 396, 963, 946, 760, 458, 390, 70, 698, 
846, 979, 597, 410, 194, 888, 97, 852, 770, 572, 
623, 453, 323, 941, 876, 99, 5, 129, 868, 552, 146, 
231, 949, 268, 755, 608, 705, 504, 635, 392, 970, 
654, 785, 295, 761, 684, 146, 482, 162, 541, 818, 
622, 828, 724, 232, 568, 807, 569, 580, 864, 709, 
217, 594, 687, 167, 248, 447, 27, 339, 341, 921, 
508, 923, 962, 430, 240, 62, 688, 212, 176, 478, 
664, 871, 219, 398, 889, 577, 312, 827, 365, 33, 
677, 751, 506, 658, 848, 717, 321, 400, 180, 561, 
926, 515, 932, 839, 828, 997, 355, 42, 334, 854, 
884, 599, 93, 393, 399, 246, 825, 553, 456, 181, 
564, 64}

% selects all elements that are smaller or equal to 97
\Preselect{\LstLong}{97}{\mylist}
\mylist

\MemberQ{\mylist}{5}
5 is \ifmember\else not\fi in the list

\MemberQ{\mylist}{6}
6 is \ifmember\else not\space\fi in the list


% selects all elements that are smaller or equal to 50 and sorts them,
% but is this the output you want
\Hits{\mylist}{50}{\hitlist}
\hitlist
\end{document}

Just for completeness: a membership test that is not restricted to integers. (I am sure that there are many features such as expandibility and so on which this does not have but it does not require packages and seems to be reasonably fast. I I knew what "expandable" means precisely, I may be able to appreciate this feature more. ;-)

\documentclass{article}
\newif\ifmember
\makeatletter% for \@for see e.g. https://tex.stackexchange.com/a/100684/121799
\newcommand{\MemberQ}[2]{\global\memberfalse%
    \edef\temp{#2}%
    \@for\next:=#1\do{\ifx\next\temp\relax\global\membertrue\fi}}
\makeatother
\begin{document}

\MemberQ{a,4,7,11}{11} \ifmember in\else out \fi

\MemberQ{a,4,7,11}{3} \ifmember in\else out \fi

\MemberQ{a,4,7,11}{A} \ifmember in\else out \fi

\MemberQ{a,4,7,11}{a} \ifmember in\else out \fi

\end{document}
|improve this answer|||||
  • Testing for a single element takes O(N) time. Doing that a lot of times, namely 1, ..., n where n is the biggest number that can occur in the list takes O(n²) time. Please also see my updated answer for more context. – siracusa Jul 4 '19 at 20:03
  • 1
    @siracusa What marmot@ is pointing out is that we don't have to test separately for each element. We can, in one pass, first extract all numbers less than n. – ShreevatsaR Jul 4 '19 at 23:12
  • @ShreevatsaR The list only includes numbers less or equal to n in the first place, so the filtering would give the same result. I don't see a way to get rid of the membership test for each number from 1, ..., n – siracusa Jul 5 '19 at 0:23
  • @siracusa I added a code that addresses your updated question. – user121799 Jul 5 '19 at 5:53
  • 1
    @siracusa It really depends on what you want to do with the information. My point is really that you can bring it down to linear. Yes, in the update I build a large array, but depending on what you really need to do this may not be necessary. That is to say that if you only need to use these tests once, you can embed whatever you want to do with the information in the loop. (In a way Joseph's answer already proofs that there is no necessity to have a quadratic dependence since after all even core level macros cannot defy mathematics. ;-) – user121799 Jul 5 '19 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.