0

我最近制作了一个自行车旅行分析器，您可以在其中输入您的行程距离和该行程的平均速度，它会计算您的时间，将您当前的速度与您输入的所有速度的最低速度、最高速度和平均速度进行排名。 ，然后按速度、距离和时间绘制您的进度（最近 10 次行程）。事情一直在按计划进行，除了当我不得不删除记录（那是不正确的记录）并正常运行程序时（由于数据库对索引所做的事情，编号全部搞砸了）。我添加了一个函数来帮助缓解其中的一些问题，但它并没有完全解决这个问题。（它不会准确显示 10 条记录，因为在指定的间隔上缺少一些记录号。）所以现在，我正在改进它，并找到了两种方法。

我找到了一种简单的递归方式，以及相应的迭代方式。

递归方式：

private int calculateOffset(int min, int max)
{
    int actualTripNumber = 0, expectedTripNumber = 0, totalOffset = 0;
    try
    {
        resultSet = statement.executeQuery("SELECT TripNumber FROM BikeTripRecords WHERE TripNumber > " + 
            ((max == 0) ? String.format("(SELECT max(TripNumber) FROM BikeTripRecords) - %d", maxShowableRecords) : 
                String.format("%d AND TripNumber < %d", min, max))
            );
        //we could set expectedTripNumber = min + 1 (and then offset = min + 1), but that would cost one instruction
        while (resultSet.next())
        {
            actualTripNumber = resultSet.getInt(1);     //get the actualTripNumber
            totalOffset += ((expectedTripNumber > 0) ? actualTripNumber - expectedTripNumber : actualTripNumber - (min + 1));   //calculate the offset
            expectedTripNumber = actualTripNumber + 1;  //we expect the next actualTripNumber to be one more than the current one
        }
    }
    catch (SQLException exception)
    {
        exception.printStackTrace();
        return -1;  //You KNOW something went wrong with a negative return value; this could be replaced by System.exit(1), however
    }

    //conditional tail recursion; this should end with the last recursive call to return 0
    if (totalOffset > 0)
    {
        //if this function was called from the outside 
        if (max == 0)
        {
            //we assign to max the first number from the resultSet
            int newMax = resultSet.getInt(1);
            totalOffset += calculateOffset(newMax - totalOffset, newMax);
        }
        else
        {
            totalOffset += calculateOffset(min - totalOffset, min);
        }
    }
    return totalOffset;
}

迭代方式：

private int calculateOffset()
{
    //This version of calculateOffset() will be ITERATIVE, not recursive (and will use a helper function)
    int totalOffset = 0, intervalOffset = 1000; //giving intervalOffset a garbage value (so that we could use it in the while loop)
    int minimum = 0, maximum = 0;
    //this is the first calculation; we obtain the max(TripNumber) from BikeTripRecords (this method will only be called ONCE)
    try
    {
        resultSet = statement.executeQuery("SELECT max(TripNumber) FROM BikeTripRecords");
        resultSet.next();
        maximum = resultSet.getInt(1);  //fetching maximum
        minimum = maximum - maxShowableRecords;     //while we are at it, we might as well assign minimum a value here, too...
        }
    catch (SQLException exception)
    {
        exception.printStackTrace();
        return -1;  // You know something went wrong when the return value is negative!!
    }
    //we simply add to totalOffset the return value of our helper function (the offset of the intervals specified) while it doesn't return 0
    while (intervalOffset > 0)
    {
        intervalOffset = getIntervalOffset(minimum, maximum);   //get the intervalOffset
        totalOffset += intervalOffset;      //add it to the totalOffset
        //recalculate maximum, minimum
        maximum = minimum;
        minimum -= intervalOffset;
    }
    return totalOffset;
}

//helper function
private int getIntervalOffset (int min, int max)
{
    int offset = 0; //the value of this variable will be the return value (if everything goes according to plan)
    int actualTripNumber = 0, expectedTripNumber = 0;
    try
    {
        resultSet = statement.executeQuery(String.format("SELECT TripNumber FROM BikeTripRecords WHERE TripNumber > %d AND TripNumber <= %d", min, max));
        //computing the offset of the interval
        while (resultSet.next())
        {
            actualTripNumber = resultSet.getInt(1);     //getting the actualTripNumber
            //the only offset there should be the first time around should be the difference between the actualTripNumber and one more than the min
            //otherwise, the offset should be the difference between the actualTripNumber and the expectedTripNumber
            offset += ((expectedTripNumber > 0) ? actualTripNumber - expectedTripNumber : actualTripNumber - (min + 1));    
            expectedTripNumber = actualTripNumber + 1;  //the expectedTripNumber should be one more than the actualTripNumber
        }
    }
    catch (SQLException exception)
    {
        exception.printStackTrace();
        return -1;  // How you KNOW something went wrong....
    }
    return offset;
}

两个代码片段都检查了 k 个区间（k 是正整数）。我被难倒的是每种方法的算法复杂度的计算。两种方式的关键部分完全相同：一个 while 循环恰好执行 10-m 次（其中 m 是正在检查的间隔中计算出的缺失记录数）。在这里，我们可以肯定地说 m 以 10 为界。我想出的两种方法都是关于 k 和 sum(mj, j 在 1 和 k 之间) 的线性复杂度，即 32k-(2+递归方式为 3 sum (mj, j between 1 and k-1)) 和 4+31k-3 sum (mj, j between 1 and k-1)。（这里，mj 读作“m sub j”。）两种算法的复杂性会被摊销还是 O(max{k, sum(mj, j between 1 and k-1)})？

4

2 回答 2

1

为什么不让自己头疼，只获得 10 个最新结果呢？

由于您使用的是 derby，因此您可以通过以下方式限制结果：

statement.setMaxRows(10);

然后，假设您的TripNumber列是自动递增的 id，您可以对结果进行排序：

SELECT TripNumber FROM BikeTripRecords 
ORDER BY TripNumber DESC
于 2013-07-29T19:51:57.300 回答
0

对于递归方法，我必须在 try 块的开头添加以下代码：

if (max == 0)
{
    resultSet = statement.executeQuery("SELECT max(TripNumber) FROM BikeTripRecords");
    resultSet.next();
    min = resultSet.getInt(1);
}

这可能是不好的代码实践，因为

  • 我不得不多次说“SELECT max(TripNumber) FROM BikeTripRecords”
  • min并且max第一次未使用！

看到这一切，我只是决定采用迭代方法，因为它是这里阻力较小的路径。

另外，我刚刚收到了我的“啊哈！” 时刻：resultSet.next()从开始到完成，这两种方法都将准确返回 10 次，因此两种方法的临界区的复杂度均为 30。因此，两种方法都是摊销的。尽管如此，我仍然使用迭代方法，因为它是更好的做法。

于 2013-07-29T20:37:43.363 回答