Together::spread() hands a whole scope (one row with gaps, then an area, then a section) to SeatingShareOut::shareOut(). Where the requested tariffs price different grades that goes through shareOutByMatching(), which walks the places in house order and takes the earliest eligible one for each tariff. It answers the question it was written for, which is feasibility, and it has no notion of how far apart the places it picked end up.
So a party across several tariffs is seated in whichever part of the scope each grade happens to appear first, and the rung reports its closeness from the scope rather than from the result.
A party of 4 + 4 + 4 across three tariffs pricing three grades, in a section whose row A carries grade 5 at positions 1 to 6 and grade 6 at positions 7 to 13, was seated on positions 1, 2, 3, 4 and 7, 8, 9, 10, leaving positions 5 and 6 empty between the two groups. Taking positions 3, 4, 5, 6 for the first tariff gives one unbroken run of eight for the same two tariffs. Both answers report the same closeness.
Candidates already arrive ordered by section, row and position, so a contiguous window of that list is a compact set of seats and the search space is windows rather than subsets.
adjacent() is left alone: a true contiguous run is already the compact answer and is tried first. nearTheParty() is left alone too, because it already passes a distance-ordered list and the matcher honours input order. This is specifically the last-resort rung, which is the one that was not compactness-aware.
Today's path is O(party), not O(hall): both share-out paths stop as soon as every slot is filled, so when the first eligible places work they touch a party's worth of candidates and return. A window sweep is O(hall), so replacing the current call outright would be a regression on the common case even though the constant is small.
adjacent() has already ruled out a contiguous run, so it is returned without reading the scope again.That leaves the common path with one extent measurement added, and spends a linear pass only on the case that is currently wrong. No new query either way: this all runs on the candidate array the rung already holds.
To be settled by the propose benchmark (A/B in one process, no database) over a full hall across a single tariff at quantity 1 and 4, a mixed 4 + 4 + 4, and a nearly full hall where this rung is actually reached, with the statement count asserted as a maximum rather than an equality since it has to hold on both SQLite and MySQL. If the swept path measures worse than today, the design changes rather than shipping with a caveat.
Where a venue's grades are separate zones, a party across three of them cannot sit together and the promise can only be "as close as the price bands allow". This is worth doing for a hall that interleaves grades within a row, which the bundled example does.
Show commandsStart within a Git clone of the project using the version control instructions.
Or, if you do not have SSH keys set up on git.drupalcode.org:
compare
Comments
Comment #2
mably commentedClosing as won't fix. Two designs were built and measured against the real Auditorium hall, and neither is worth having. Recording both so nobody spends the time again.
The defect is real, but small
On a hall whose grades alternate along a row, a party of four across two categories was seated over eight positions of one row where four adjacent seats existed. So the complaint in the summary stands. What the measurements changed is the judgement of whether fixing it is worth anything.
Attempt 1: rank contiguous windows by the window's width. Does not work.
Candidates arrive in house order, so a contiguous window of them is a compact set of seats; sweep two pointers for the windows that could serve the tariffs, rank by the window's extent, run the matcher inside the best.
On section 16 the tightest window that can serve three categories measures [2 rows, span 10], while the answer
shareOut()already gives measures [2, 9]. The approach is beaten by the code it was meant to improve.The reason is structural, not a tuning problem: the window bounds the region the matcher may choose from, and the seats it picks inside it are what a booker experiences. Those are different objects, and the wrong one was being ranked. The arrangement the hall actually allows puts cat 1 at row A 3-6 and cat 3 at row B 8-11; any contiguous window holding both must also hold everything between them, so window enumeration cannot reach it at any ranking.
Cost when it did nothing: +0.045 ms worst case on mixed-tariff bookings, protected paths unchanged. Measured on a 1422-seat hall, 40 calls per figure.
Attempt 2: one run per tariff, chosen to sit near each other. Works, far too slow.
Enumerate the runs of each tariff's own grades long enough to hold its count, then take one run per tariff minimising the combined extent. This does reach a better answer than today: [2, 7] against [2, 9].
Measured on section 16, 200 calls per figure:
shareOut()over the area: 0.109 msRuns overlap (positions 1-4, 2-5, 3-6 are three runs), so the product is thousands of combinations rather than the handful it looks like. Branch-and-bound on partial extent would cut it, by an unmeasured amount.
Why it was still not worth building
The improvement the metric promises is not obviously an improvement for a person. Today, a 4 + 4 + 4 in section 16 gets four seats in row A, a two-seat gap, four more in row A, and four in row B. The tighter answer gets four seats in row A and eight unbroken in row B, which splits the first category off on its own row. Neither is plainly the better evening, and the second one is what the objective function prefers rather than what a booker asked for.
The Auditorium also has little room to gain: cat 1's grade exists only in row A and cat 3's only from row B, so a party across all three must span two rows whatever is chosen. The slack above the current answer is one row-span.
If this is ever reopened
web/tmp/bench/propose-bench.php(git-ignored), which A/Bs two copies of the strategy in one process and asserts identical seats and closeness, plusreal-hall.phpandruns-per-tariff.phpfrom this work.The numbering defect that this issue was split off from is #3615672: Read a row's seat order from the venue drawing, so a curved row stops claiming its two ends are adjacent, fixed and merged: that was the real cause of parties being seated apart, and it moved the reported booking's widest pair from 650 to 412 map units.