Saturday, October 4, 2014

On efficient algorithms for finding the goddamn endnotes

Introduction

In many recent books, the goddamn endnotes are numbered sequentially within each chapter, but chapter numbers seldom appear in the header on each page.  So a reader who wants to find a goddamn endnote typically has to search backward to figure out which chapter they are reading before they can find the goddamn endnote.  Several simple changes can make this process more efficient and less infuriating.

In this paper, we present a novel algorithm for finding a goddamn endnote (FGE) in O(1) time; that is, time bounded by a constant regardless of the size or number of chapters.

Background

The most widely deployed algorithm for FGE requires O(n+m) time; that is, time proportional to either n, the number of pages in a chapter, or m, the number of chapters, whichever is larger.  The following pseudocode sketches this algorithm:

1) Store the endnote number you want to find as e.
2) Figure out what chapter you are reading by searching for the beginning of the chapter, and store the result as c.
3) Find the footnotes at the end of the chapter and find the footnotes for chapter c.
4) Look up footnote e.

The most common implementation of Step 2 is linear in n, the number of pages in the chapter.  Some readers can execute a binary search by comparing chapter titles in the header, reducing search time to O(log n).

Similarly, the most common implementation of Step 3 is linear in m, the number of chapters, but some readers perform a binary search.

Assuming that the number of footnotes in a chapter is bounded by a constant, we consider Step 4 to be constant time.

Alternatives

1) Put the goddamn chapter number (GCN) in the goddamn header.  This simple change immediately reduces Step 2 to constant time.

2) Number the goddamn endnotes from the beginning to the end of the book.  Do not start over at the beginning of each goddamn chapter.  This change also reduces Step 2 to constant time, but with this change Step 4 may no longer be considered constant time.

3) Along with the endnote number, e, also include p, the page where the goddamn endnote appears. This change makes Step 2 constant time; and Step 3, although technically log time, practically constant time for most readers.

4) Put the goddamn endnotes at the bottom of the goddamn page (cf. footnotes).  For a bounded page size, looking at the bottom of the page is a constant time operation.

Recommendations

We recommend that publishers replace existing linear-time algorithms with any of several easy-to-implement, efficient alternatives, goddammit.

3 comments:

  1. Thanks! However, I would be happy already if the authors would write only the necessary, but (for most readers) uninteresting information in the goddamn endnotes, like bibliographical or legal stuff. I hate to always keep a finger or a second bookmark, which must be synchronized with the primary bookmark, in the last few pages, just because the author didn't know how to fit the very interesting additional information (VIAI) or further explications in the main text.

    ReplyDelete
    Replies
    1. Good point. I would love to see some kind of typographical distinction between GD endnotes that contain VIAI and the ones that just have BI (bibliographical information).

      Delete
  2. If only authors and publishers would meet the spirit of the discipline of scholarship as well as its letter. Just make a bibliography. I have a small collection of memorable and valuable bibliographies that I've copied. Some authors divide up their bibliographies into useful segments (for example, by primary/secondary sources, periodicals, etc.). Those authors have my deepest gratitude (and respect).

    ReplyDelete