高效地在不使用索引的情况下搜索数组?

huangapple go评论83阅读模式
英文:

efficiently searching arrays without using index?

问题

以下是翻译好的部分:

所以我正在为一门课程制作基于文本的角色扮演游戏(RPG)。目前功能在一个房间中运行,这是我目前想要的全部。然而,我想要一种更有效的方法来做这个。我想要在不使用索引的情况下实现这一点。我想要从包含(3.a)到end.3的文本文件中的元素列表。你们有没有任何经验的人可以帮助我?这是我第一次尝试这种类型的项目。我之所以这么早就问这个问题,是因为这是项目的介绍部分,而学期末的最终项目将是一个解析的40页文本文件。

文本文件:

1.a

建筑外部
-------
西部     2
上部     2
北部     3
内部     3

end.1

2.a

路的尽头
你在一条道路的尽头,位于一个小山顶上。
你可以看到山谷东边有一座小建筑。
------
东部     1
下部     2

end.2

3.a

建筑内部
你在一个建筑物内部,一个大泉水的井房。
-------
南部     1
外部     1

end.3

代码部分:

public static void main(String[] args) throws FileNotFoundException { 
		
    int direction = 0;
    Scanner s = new Scanner(new File("C:\\Users\\Basil Sheppard\\eclipse-workspace\\software practice\\src\\software\\rooms.txt"));
    Scanner choice = new Scanner(System.in);
    ArrayList<String> listS = new ArrayList<String>();
    
    while (s.hasNextLine())
        listS.add(s.nextLine());
    
    System.out.println("请输入3进行测试");
    direction = choice.nextInt();
    
    switch (direction) {
    
        //测试房间3
        case 3: {
            boolean found = listS.contains("3.a");
            if (found) {
                for (int i = 22; i < 27; i++) {
                    System.out.println(listS.get(i));
                }
            }
        } 
        // 其他情况...
    }
}

请注意,我已经删除了代码中的HTML实体编码,这样它就不会在翻译中显示出来。如果你需要更多帮助,请随时提问。

英文:

So I am making a text based rpg for a class. Currently the functionality is working for one room which is all I currently want. However I want a more efficient way of doing this. I want to do this without indexes. I want to print a list of elements from the text file from contains(3.a) to the point where end.3 is. Can any of you vets help me? . This is my first attempt at this type of project. The reason I am asking this early is because this is the intro into the project and the final project at the end of the semester will be a parsed 40 page text file.

The text file

1.a

Outside building
-------
WEST       2
UP         2
NORTH      3
IN         3

end.1

2.a

End of road
You are at the end of a road at the top of a small hill.
You can see a small building in the valley to the east.
------
EAST      1
DOWN      2

end.2

3.a

Inside building
You are inside a building, a well house for a large spring
-------
SOUTH    1
OUT      1

end.3

The code

public static void main(String[] args)throws FileNotFoundException{ 
	
	
	int direction = 0;
	Scanner s = new Scanner(new File(&quot;C:\\Users\\Basil Sheppard\\eclipse-workspace\\software practice\\src\\software\\rooms.txt&quot;));
	Scanner choice = new Scanner(System.in);
	ArrayList&lt;String&gt; listS = new ArrayList&lt;String&gt;();
	

	while ( s.hasNextLine()) 
		listS.add(s.nextLine());
	
	
	System.out.println(&quot;please enter 3 for testing&quot;);
    direction = choice.nextInt();

	switch (direction){

//tests for room 3	
	case 3: {
	boolean found = listS.contains(&quot;3.a&quot;);
    if(found) {
    	for(int i = 22; i&lt;27; i++) {
	        System.out.println(listS.get(i));
	    }
    }
   			 				
} 

答案1

得分: 1

你的方法看起来完全错误。

我会这样做:

  1. 创建一个名为 MapLocation 的类,包括以下内容:
    1. 标题,String
    2. 描述,String[]
    3. 导航,MapNavi[]
  2. 创建另一个名为 MapNavi 的类,包括以下内容:
    1. 地图位置,int
    2. 方向,String
  3. 将整个文件读取并解析为 MapLocation[]
  4. 处理输入并遍历 MapLocation[]

文件的结构似乎是:

(#.a

标题
描述行*
-------
MapNavi+

end.#)+

因此,你可以构建一个解析器来按照上述方式处理文件,这相当简单。你也可以仅使用正则表达式来解析整个文件。

示例解析器:

try (BufferedReader br = new BufferedReader(new InputStreamReader(getClass().getResourceAsStream(_FILE_NAME))))
{
    String line;
    int state = 0;
    MapLocation currSegment = null;
    while ((line = br.readLine()) != null)
    {
        switch (state)
        {
        case 0:
           if (line.endsWith(".a"))
           {
               String segId = line.substring(0, line.indexOf(".a"));
               currSegment = new MapLocation(Integer.parseInt(segId));
               state++;
           }
           break;
        case 1:
           if (line.length() != 0)
           {
               currSegment.setTitle(line);
               state++;
           }
        case 2:
           if ("-------".equals(line))
           {
               state++;
           } else if (line.length() > 0)
           {
               currSegment.addDescription(line);
           }
        case 3:
           if (line.equals("end." + currSegment.getSegId()))
           {
               mapLocations.put(currSegment.getSegId(), currSegment);
               currSegment = null;
               state = 0;
           } else if (line.length() > 0)
           {
               String[] nav = line.split("\t");
               Integer mapLoc = Integer.parseInt(nav[1]);
               currSegment.addNavi(mapLoc, nav[0]);
           }
        }
    }
}

一旦文件被解析到 mapLocations 容器中,你就可以准备处理输入:

try (Scanner in = new Scanner(System.in))
{
    MapLocation currLoc = // 起始位置;
    while (!quitSignal.equals(line = in.nextLine()))
    {
        int mapLoc = Integer.parseInt(line);
        if (currLoc.validateNav(mapLoc))
        {
            currLoc = mapLocations.get(mapLoc);
            System.out.println("你前往了" + currLoc.getTitle());
            System.out.println(currLoc.toString());
        }
        else
        {
            System.out.println("你不能从这里前往位置'" + line + "'。请重新选择目的地。");
        }
    }
}
英文:

Your approach looks entirely wrong.

What I would do:

  1. Create a class MapLocation, with the following:
    1. Title, String
    2. Description, String[]
    3. Navigation, MapNavi[]
  2. Create another class MapNavi, with the following:
    1. MapLoc, int
    2. Direction, String
  3. Read and parse entire file into MapLocation[]
  4. Process input and traverse MapLocation[]

The structure of the file seems to be:

(#.a
Title
Description Lines*
-------
MapNavi+
end.#)+

So you could either build a parser to process the file as above, which is quite trivial. You could also parse the entire file using purely RegEx.

Sample parser:

try (BufferedReader br = new BufferedReader(new InputStreamReader(getClass().getResourceAsStream(_FILE_NAME))))
{
String line;
int state = 0;
MapLocation currSegment = null;
while ((line = br.readLine()) != null)
{
switch (state)
{
case 0:
if (line.endsWith(&quot;.a&quot;))
{
String segId = line.substring(0, line.indexOf(&quot;.a&quot;));
currSegment = new MapLocation(Integer.parseInt(segId));
state++;
}
break;
case 1:
if (line.length() != 0)
{
currSegment.setTitle(line);
state++;
}
case 2:
if (&quot;-------&quot;.equals(line))
{
state++;
} else if (line.length() &gt; 0)
{
currSegment.addDescription(line);
}
case 3:
if (line.equals(&quot;end.&quot; + currSegment.getSegId()))
{
mapLocations.put(currSegment.getSegId(), currSegment);
currSegment = null;
state = 0;
} else if (line.length() &gt; 0)
{
String[] nav = line.split(&quot;\t&quot;);
Integer mapLoc = Integer.parseInt(nav[1]);
currSegment.addNavi(mapLoc, nav[0]);
}
}
}
}

Once the file is parsed into the mapLocations container, you are ready to process input:

try (Scanner in = new Scanner(System.in))
{
MapLocation currLoc = // startLocation;
while (!quitSignal.equals(line = in.nextLine()))
{
int mapLoc = Integer.parseInt(line);
if (currLoc.validateNav(mapLoc))
{
currLoc = mapLocations.get(mapLoc);
System.out.println(&quot;You travel to &quot; + currLoc.getTitle());
System.out.println(currLoc.toString());
}
else
{
System.out.println(&quot;You cannot travel to location &#39;&quot; + line + &quot;&#39; from here.  Please re-select your destination.&quot;);
}
}
}

答案2

得分: 0

你应该考虑将你的路径存储为一个xml文件!Java有一些很酷的方法来读取它们,并且可以理解列表中的元素。你甚至可以写入xml以更轻松地构建你的游戏。查看这个链接以了解如何读取xml:https://stackoverflow.com/a/428091/9789673

英文:

You should look into storing your path as an xml file! Java has some cool ways to read them and it can understand elements in a list. You can even write to xml for easier constructing your game. Check this out for how to read in xml: https://stackoverflow.com/a/428091/9789673

答案3

得分: 0

尝试这个。

try (Scanner s = new Scanner(new File("C:\\Users\\Basil Sheppard\\eclipse-workspace\\software practice\\src\\software\\rooms.txt"))) {
    Scanner choice = new Scanner(System.in);
    ArrayList<String> listS = new ArrayList<String>();

    while (s.hasNextLine())
        listS.add(s.nextLine());

    System.out.println("请输入 3 进行测试");
    int direction = choice.nextInt();

    listS.stream()
        .dropWhile(x -> !x.equals(direction + ".a"))
        .takeWhile(x -> !x.equals("end." + direction))
        .forEach(System.out::println);
    System.out.println("end." + direction);
}

输出结果

3.a
建筑内部
您在建筑物内部,这是一个大泉水的井房
-------
南方    1
出口      1
end.3

请注意,.takeWhile(x -> !x.equals("end." + direction)) 会忽略 end.3 本身。

英文:

Try this.

try (Scanner s = new Scanner(new File(&quot;C:\\Users\\Basil Sheppard\\eclipse-workspace\\software practice\\src\\software\\rooms.txt&quot;))) {
Scanner choice = new Scanner(System.in);
ArrayList&lt;String&gt; listS = new ArrayList&lt;String&gt;();
while (s.hasNextLine())
listS.add(s.nextLine());
System.out.println(&quot;please enter 3 for testing&quot;);
int direction = choice.nextInt();
listS.stream()
.dropWhile(x -&gt; !x.equals(direction + &quot;.a&quot;))
.takeWhile(x -&gt; !x.equals(&quot;end.&quot; + direction))
.forEach(System.out::println);
System.out.println(&quot;end.&quot; + direction);
}

output

3.a
Inside building
You are inside a building, a well house for a large spring
-------
SOUTH    1
OUT      1
end.3

Note that .takeWhile(x -&gt; !x.equals(&quot;end.&quot; + direction)) discards end.3 itself.

答案4

得分: -1

我认为你需要考虑两个主要因素:

  • 结构化你的文件,使其行具有相对一致的结构,易于解析。
  • 思考如何组织你的代码,以便你只需要在文件中进行一次扫描,创建类来在第一次读取文件时以有组织的方式将数据存储在内存中。换句话说,在某种程度上,这是一个“索引”,但你不能两者兼得:要么你在第一次扫描时存储/索引文件中的信息,要么你将信息丢弃,下次查询时必须再次扫描文件,这在本质上是低效的。

例如,你可以像这样结构化你的文件:

BEGIN:LOCATION:1
BEGIN:DESCRIPTION:
A house.
END:DESCRIPTION
BEGIN:DIRECTIONS
NORTH:3
SOUTH:4
END:DIRECTIONS
END:LOCATION

换句话说,这些行通常由'command':'subcommand'组成,而且在给定文件的一行后,将其相对容易分割为其组件(查看String.indexOf()、String.substring())。如果可以的话,可以查看正则表达式 API:查看 Pattern 和 Matcher 类。 (从理论上讲,当你试图同时为多个不同的模式/子字符串扫描相同的行/文本时,这可以带来一些效率提升,并且在处理更复杂的模式/命令的大量文本扫描时通常会使用这种方法。对于你的目的,如果你发现使用简单的 String 方法(如 indexOf()、substring() 等)更容易掌握,那也完全可以。)

其他人提到了 XML:这是一种你也可以考虑的结构化格式,它带有内置在Java平台中的标准解析例程的优势。但如果你设计的格式一致且编写解析例程容易,那么使用纯文本文件也没有本质上的问题...

英文:

I think you need to think about two main things:

  • Structure your file so that its lines have a fairly consistent structure that is easy to parse.
  • Think about how you can organise your code so that you only scan through the file once, creating classes to store the data in memory in an organised way the first time you read through the file. (Yes, in a sense, this is an "index", but you can't have it both ways: either you store/index information from the file the first time you scan it, or you throw the information away and have to scan through it again on the next query, which is inherently inefficient.)

For example, you might structure your file something like this:

BEGIN:LOCATION:1
BEGIN:DESCRIPTION:
A house.
END:DESCRIPTION
BEGIN:DIRECTIONS
NORTH:3
SOUTH:4
END:DIRECTIONS
END:LOCATION

In other words, the lines generally consist of 'command':'subcommand', and given a line in the file, it is fairly easy to split this into its components (look at String.indexOf(), String.substring(). If you can, look at the regular expressions API: see the Pattern and Matcher classes. (Theoretically, this can bring some efficiencies when you are trying to scan the same line/text for a number of different patterns/substrings simultaneously, and is the approach you'd generally use if you were scanning large volumes of text for more complex patterns/commands. For your purposes, you would also be fine with the simple String methods-- indexOf(), substring() etc-- if you find these easier to get to grips with.)

Others have mentioned XML: this is one a structured format that you could also consider, and comes with the advantage of standard parsing routines built into the Java platform. But there's nothing inherently wrong with a plain old text file in a format that you've devised so long as it's consistent and it's easy to write a routine to parse it...

huangapple
  • 本文由 发表于 2020年8月20日 04:45:11
  • 转载请务必保留本文链接:https://go.coder-hub.com/63494745.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定