# Probability Density Estimation through Nonparametric Adaptive Partitioning and Stitching
## 3 Results and Discussions
### Computation Time  
To evaluate the computational efficiency of NAPS and NMEM, we measured the total computation times for all eight distributions at sample sizes ranging from \(2^{9}\) to \(2^{22}\). On our hardware, our current C++ NMEM implementation can reliably provide estimates up to \(N=2^{22}\) for a wide range of distributions with default settings, although the quality of  
Figure 10: Scaled quantile residual comparisons: The SQR calculations for single estimates from a Beta(2, 0.5) distribution for (**a**) NAPS \(SQR(u)\) for \(N=2^{11}\). (**b**) NMEM \(SQR(u)\) for \(N=2^{11}\). (**c**) NAPS \(SQR(u)\) for \(N=2^{18}\). (**d**) NMEM \(SQR(u)\) for \(N=2^{18}\). estimate can deteriorate for difficult cases. For the NAPS implementation, we consider two cases: serial using a single processor and parallel using 40 processors. In the parallel processing case, we extend the largest sample size by more than an order of magnitude to \(2^{27}\), but this size does not reflect hardware or implementation limits. However, for the series case using a single processor, memory limitations sets a sample size limit to \(2^{25}\). Figure 10(a) shows the wall time (total elapsed time) averaged over 100 trials for sample sizes up to \(2^{22}\) for both methods, and 10 trials for \(2^{23}\) to \(2^{25}\) for NAPS (serial). The times are also averaged over all eight distributions, with error bars indicating the variation across distributions. The variation in NMEM is noticeably larger than NAPS, especially for large sample sizes. This is expected because, by separating the data into more uniform density blocks, the wall time in NAPS is dictated more by the number of blocks than the details of the original distribution. As predicted, the time to compute all the blocks in NAPS, even when run in serial, is typically less than processing all the data together with NMEM. These times include the overhead of separating the blocks and stitching the estimates together. Figure 10(b) displays a dashed line representing the average wall time across 10 trials and the eight distributions for NAPS run with 40 processors. The NMEM and NAPS (serial) data shown in Figure 10(a) is re-shown, but without the error bars for clarity. Note that the results are identical for NAPS serial versus parallel with the same seed for the random number generator. The NMEM wall time begins to level off around a sample size of \(2^{18}\), primarily due to the more challenging distributions that NMEM struggles to estimate effectively. NMEM has safeguards implemented that will abort its random search procedure to optimize Lagrange multipliers when it becomes clear that progress towards an improved estimate is not being made at a sufficiently fast rate. While the hardware limit on memory when running NAPS in serial is larger than the limit of NMEM as a one-shot method since block sizes are smaller, the information for all blocks still needs to be stored. This results in a modest increase in the memory limit for NAPS (serial). This practical hardware limitation is further increased when the blocks are distributed among multiple processors, resulting in significant time savings and the ability to increase the sample size. Here, we show results up to sample sizes of \(2^{27}\). This is not due to a hardware limit on the sample size but rather a practical limit in available computing resources. Additional processors and memory would allow for substantial increases in sample size beyond \(2^{27}\). Ongoing work includes the optimization of data structures combined with parallel computing implementations in C++ for a future update release on our user-friendly software in C++, R and MATLAB, and a first Python version. These software updates will include hardware aware modes of operations.