论文标题
使用数据结构的渐近实验：两部分图匹配和覆盖
Asymptotic Experiments with Data Structures: Bipartite Graph Matchings and Covers
论文作者
论文摘要
我们考虑了三个项目中的两分图和许多渐近性能实验的实例：（1）电影列表，电影和观众的数据库，（2）最大匹配项以及（3）最小设置盖。实验旨在测量三种编程语言中抽象数据类型（ADT）的渐近运行时性能：Java，R和C ++。这些实验的结果可能令人惊讶。在项目（1）中，R中最好的ADT始终优于公共域Java库中的所有ADT，包括Google的库。最大的电影列表具有$ 2^{20} $标题。在项目（2）中，R中的Ford-Fulkerson算法实现明显优于Java。最难的实例有88452行和729列。在项目（3）中，在R中，贪婪算法的随机版本可以大大优于C ++中最新的随机求解器，该实例与$ num \ _ROWS \ ge 300 $和$ num \ num \ _columns \ ge 3000 $。
We consider instances of bipartite graphs and a number of asymptotic performance experiments in three projects: (1) top movie lists, given databases of movies and viewers, (2) maximum matchings, and (3) minimum set covers. Experiments are designed to measure the asymptotic runtime performance of abstract data types (ADTs) in three programming languages: Java, R, and C++. The outcomes of these experiments may be surprising. In project (1), the best ADT in R consistently outperforms all ADTs in public domain Java libraries, including the library from Google. The largest movie list has $2^{20}$ titles. In project (2), the Ford-Fulkerson algorithm implementation in R significantly outperforms Java. The hardest instance has 88452 rows and 729 columns. In project (3), a stochastic version of a greedy algorithm in R can significantly outperform a state-of-the-art stochastic solver in C++ on instances with $num\_rows \ge 300$ and $num\_columns \ge 3000$.
