这篇论文教你怎么在Desbordante里用C++重写FASTOD和ORDER算法，速度飙到10倍，内存省近3倍，搞数据清洗和查询优化的可以看看。
本文研究两种OD发现算法FASTOD和ORDER，并在C++中重新实现以提升性能。在Desbordante开源数据剖析工具中集成后，重新实现版本性能提升最高3倍。结合所提优化技术，性能进一步提升至10倍，内存消耗降低2.9倍。这些改进使顺序依赖发现更贴近工业应用。
Order in Desbordante: Techniques for Efficient Implementation of Order Dependency Discovery Algorithms
Science-intensive data profiling focuses on discovery and validation of various patterns in datasets. This study considers discovery of one such pattern - order dependency (OD). Simply put, OD states that some list of columns is ordered according to another one. It is of use for database query optimization, data cleaning and deduplication, anomaly detection, and much more. Existing discovery methods have approached this problem solely from the algorithmic standpoint, without focusing on the implementation side. At the same time, this problem is very computationally intensive, and therefore this part should not be ignored, as it brings ODs closer to industrial use. In this paper, we study two algorithms for OD discovery which target different OD axiomatizations - FASTOD and ORDER. We start by reimplementing these algorithms in C++ in order to speed them up and lower their memory consumption. We then analyze their bottlenecks and propose several techniques which improve their performance even further. To perform evaluation, we have implemented these algorithms inside Desbordante - a science-intensive, high-performance, and open-source data profiling tool developed in C++. Experiments have demonstrated a performance improvement of up to 3x obtained by reimplemented versions, and, with the application of our techniques, up to 10x. Memory consumption has been lowered by up to 2.9x.