Explore chapters and articles related to this topic
Trees
Published in Jonathan L. Gross, Jay Yellen, Mark Anderson, Graph Theory and Its Applications, 2018
Jonathan L. Gross, Jay Yellen, Mark Anderson
Searching a sorted array using a binary search requires at worst O(log2n) computations, since each comparison eliminates half of the elements. A search through a linked list must be sequential and therefore is, in the worst case, O(n).
Modifications of the Robertson Method for Calculating Correlated Color Temperature to Improve Accuracy and Speed
Published in LEUKOS, 2023
Doug Baxter, Michael Royer, Kevin Smet
At a minimum, a LUT for CCT calculations includes a predefined sorted array of color temperature values that are accompanied by chromaticity coordinates for the corresponding Planckian radiator. Advanced methods may include more information, such as precomputed derivatives. The CCT calculation process begins by searching the LUT to find the entries for which the distance between the tabulated chromaticity coordinates and those of the test light sources are the smallest and second smallest (i.e., the CCT of the test sources is between two isotemperature lines). This works because the distance as a function of color temperature is an unimodal function with a single minimum – as long as the distance from the Planckian locus (Duv) is reasonably limited to not greater than 0.05 units. The 1968 Robertson method uses a 31-row LUT based on reciprocal megakelvin (MK−1) indices with an increment of 10 between 0 MK−1 and 100 MK−1, and 25 between 100 MK−1 and 600 MK−1. This covers the range from 1667 K to 100,000 K.
Aggregation of clans to speed-up solving linear systems on parallel architectures
Published in International Journal of Parallel, Emergent and Distributed Systems, 2022
Dmitry A. Zaitsev, Tatiana R. Shmeleva, Piotr Luszczek
The first fit on a sorted array algorithm proceeds as follows: Sort the array of items' weights in descending order.Assign the bin number i: = 0 and assign the current bin size consumed .Fill-in bin i: start with the first available item, assigning it to j = 0;if , then exclude the item j from the sorted array and assign ;if j<n and , assign j: = j + 1 and go to line 3b.If there are still items left, assign i: = i + 1 and go to line 3, otherwise finish with the current assignment.
Projections onto the canonical simplex with additional linear inequalities
Published in Optimization Methods and Software, 2022
For problems (DRO1) including the φ-divergences and for (SIMPLEX), we reduced the optimality conditions into one equation in one variable. For (DRO2) with norm, we reduced it into two equations in two variables from which λ is implicitly computed, further reducing the system into one equation in one variable. It is not difficult to show that this implicit Equation (24b) is equivalent to Since (30) is identical to (2), there are algorithms in which compute λ for any fixed µ. For simplicity, we implemented a simpler algorithm which first sorts and then finds λ in one pass through the sorted array.