小编Dav*_*son的帖子

我目前有一个简单的数据库程序，它从文本文件中读取键并将它们存储在双向链表中（如果需要，稍后会读取值）。目前，我对列表进行顺序搜索，但这显然相当慢。我希望还有另一种方法可以做到。我正在阅读有关二叉树（特别是红黑树）的内容，但我对它们不太了解，并希望我能从 stackoverflow hivemind 中看到一些东西:)我想我的问题是，最快的方法是什么在双向链表中进行搜索？

编辑：忘记说列表已排序。不知道这是否会改变什么。另外，我只读取keys的原因是最大值长度是1024*32字节，我觉得太大了。请注意，这是一项作业，因此“典型使用场景”不适用。教授们可能会对这件事进行压力测试，而我不想分配那么大的块。

我正在尝试为类编写一个数据库,其中我从文件中读取了所有键值(格式化的keyNULL BYTEvalueNULL BYTE等).我很想使用链接列表,但我得到结构没有下一个值的错误.请帮我!

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>

#include "sdbm.h"

static FILE *db;
static bool opened = false;
static int err = 0, keyLen = 8;

typedef struct {
  char *name;
  Key *next;
} Key;

static Key *head = NULL,*tail = NULL; 
/**
 * Create new database with given name. You still have
 * to sdbm_open() the database to access it. Return true
 * on success, false on failure.
 */
bool sdbm_create( const char *name …

我正在做一个简单的硬币翻转实验,课程涉及在一定数量的线程上翻转一定数量的硬币.要运行我们的加速性能测试,我们使用固定数量的coinflips(我一直使用十亿)并更改线程数.我们使用具有8个内核的AWS额外高CPU实例来运行这些测试.出于某种原因,只要我使用超过6个线程,我就会显着减速.更糟糕的是,这是不一致的.有时候我会得到14秒,有时候会得到2个相同数量的线程和翻转.这没有道理.我尝试过使用不同的JVM(OpenJRE和Sun JVM)并尝试新的实例.下面是我的代码和基准测试结果(以ms为单位).我会喜欢一些帮助.谢谢.

编辑:所以我似乎解决了它,非常感谢yadab和Bruno Reis的建议.他们建议使用局部变量来跟踪头部的数量,我认为这可能是一个因素.他们还建议在同一个JVM会话中运行我的所有测试,这几乎肯定是一个因素.谢谢大家的帮助.

Speedup:
Threads | Flips | Time
1       1000000000  16402 16399  16404
2       1000000000  8218  8216   8217
3       1000000000  5493  5483   5492
4       1000000000  4125  4127   4140
5       1000000000  3306  3304   3311
6       1000000000  2758  2766   2756
7       1000000000  8346  7874   10617
8       1000000000  14370 14414  17831
9       1000000000  14956  14764  15316
10      1000000000  13595 14491  14031
11      1000000000  12642 11188   10625
12      1000000000  10620 10629  10876
13      1000000000  8422  9950   9756
14      1000000000  9284  9546   10194 …

import javax.swing.JFrame;
import javax.swing.JPanel;
import java.awt.Frame;
import java.awt.Graphics;
import java.awt.Color;
import java.util.Random;

public class dots {
    public dots() {
        init();
    }
    public void init() {
        JFrame frame = new JFrame("Dots");
        frame.setExtendedState(Frame.MAXIMIZED_BOTH);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        JPanel panel = new JPanel();
        int scrWidth = (int) frame.getSize().getWidth();
        int scrHeight = (int) frame.getSize().getHeight();
        JFrame.getContentPane().add(panel);
        Random rand = new Random();
        Graphics g = panel.getGraphics();
        for (int i = 0; i < 18; i++) {
            g.setColor(i < 12 ? Color.YELLOW : Color.BLUE);
            g.drawOval(Random.nextInt(scrWidth),Random.nextInt(scrHeight),40,40);
        }
        frame.setVisible(true);
    }
    public static …

public static boolean isValidCoordinate(Coordinate point) {
    Point map = point.mapCoordinates, tileSet = point.tileSetCoordinates, tile = point.tileCoordinates, pixel = point.pixelCoordinates;
    if (map != null && map.x >= 0 && map.y >= 0) {
        if (tileSet != null) {
            if (tileSet.x >= 0 && tileSet.y >= 0) {
                if (tile != null) {
                    if (tile.x >= 0 && tile.y >= 0) {
                        if (pixel != null) {
                            if (pixel.x >= 0 && pixel.y >= 0) {
                                return true;
                            }
                            else {
                                return …