如何撰寫搜索函式來獲取所需檔案的路徑？-有解無憂

我有一個看起來像影像的目錄結構。如何撰寫搜索函式來獲取所需檔案的路徑？

該結構以objects. File每個物件都具有以下形式：{type:'file', name:'file a1'}例如。Folder物件類似于 File 物件，但它們有一個額外的鍵children，即子檔案夾/檔案的陣列。

rootFolder這是之前影像中物件的控制臺日志：

如何撰寫搜索函式來獲取所需檔案的路徑？

目標： 我想要的是撰寫一個搜索函式，它以陣列的形式回傳特定檔案的路徑。例如，如果我要搜索file c3，結果將是：['folder a3', 'folder b4']。

我嘗試了很多東西，但遞回并不是我的強項。

代碼可以是javascript或python；我關心的是演算法本身。

這是用于生成的代碼rootFolder：

// defining constants
const TYPES = {FILE: 'file', FOLDER: 'folder'}
const FILE_NAMES = {
  FILE_A1:'file a1', 
  FILE_A2:'file a2', 
  FILE_A4:'file a4',
  FILE_B2:'file b2',
  FILE_B3:'file b3',
  FILE_C1:'file c1',
  FILE_C2:'file c2',
  FILE_C3:'file c3',
  FILE_C4:'file c4',
  FILE_C5:'file c5',
}
const FOLDER_NAMES = {
  ROOT_FOLDER:'root folder',
  FOLDER_A3:'folder a3',
  FOLDER_B1:'folder b1',
  FOLDER_B4:'folder b4'
}
// defining classes
class File {
  constructor(type, name) {
    this.name = name
    this.type = type
  }
}
class Folder {
  constructor (type, name, children) {
    this.name = name
    this.type = type
    this.children = children
  }
}
// defining file objects
const fileA1 = new File(TYPES.FILE, FILE_NAMES.FILE_A1)
const fileA2 = new File(TYPES.FILE, FILE_NAMES.FILE_A2)
const fileA4 = new File(TYPES.FILE, FILE_NAMES.FILE_A4)
const fileB2 = new File(TYPES.FILE, FILE_NAMES.FILE_B2)
const fileB3 = new File(TYPES.FILE, FILE_NAMES.FILE_B3)
const fileC1 = new File(TYPES.FILE, FILE_NAMES.FILE_C1)
const fileC2 = new File(TYPES.FILE, FILE_NAMES.FILE_C2)
const fileC3 = new File(TYPES.FILE, FILE_NAMES.FILE_C3)
const fileC4 = new File(TYPES.FILE, FILE_NAMES.FILE_C4)
const fileC5 = new File(TYPES.FILE, FILE_NAMES.FILE_C5)
// defining folder objects
const folderB1 = new Folder(TYPES.FOLDER, FOLDER_NAMES.FOLDER_B1, [fileC1, fileC2])
const folderB4 = new Folder(TYPES.FOLDER, FOLDER_NAMES.FOLDER_B4, [fileC3, fileC4, fileC5])
const folderA3 = new Folder(TYPES.FOLDER, FOLDER_NAMES.FOLDER_A3, [folderB1, fileB2, fileB3, folderB4])
const rootFolder = new Folder(TYPES.FOLDER, FOLDER_NAMES.ROOT_FOLDER, [fileA1, fileA2, folderA3, fileA4])

console.log(rootFolder);

uj5u.com熱心網友回復：

洗掉間接

在我們開始之前，首先消除由 20 多個變數引起的無數間接性。我們可以只使用兩 (2) 個類和一個root-

class File {
  constructor(type, name) {
    this.name = name
    this.type = type
  }
}

class Folder {
  constructor(type, name, children) {
    this.name = name
    this.type = type
    this.children = children
  }
}

const root =
  new Folder("folder", "root folder", [
    new File("file", "file a1"),
    new File("file", "file a2"),
    new Folder("folder", "folder a3", [
      new Folder("folder", "folder b1", [
        new File("file", "file c1"),
        new File("file", "file c2")
      ]),
      new File("file", "file b2"),
      new File("file", "file b3"),
      new Folder("folder", "folder b4", [
        new File("file", "file c3"),
        new File("file", "file c4"),
        new File("file", "file c5")
      ])
    ]),
    new File("file", "file a4")
  ])

去除冗余

TYPES.FILETYPES.FOLDER如果您有單獨的File和Folder類，則不需要。每個實體都已經有一個關聯的型別 -

class File {
  constructor(name) { // ? type not necessary
    this.name = name
  }
}

class Folder {
  constructor (name, children) { // ? type not necessary
    this.name = name
    this.children = children
  }
}

const root =
  new Folder("root folder", [
    new File("file a1"),
    new File("file a2"),
    new Folder("folder a3", [
      new Folder("folder b1", [
        new File("file c1"),
        new File("file c2")
      ]),
      new File("file b2"),
      new File("file b3"),
      new Folder("folder b4", [
        new File("file c3"),
        new File("file c4"),
        new File("file c5")
      ])
    ]),
    new File("file a4")
  ])

多個回傳值

因為檔案系統支持具有相同名稱的檔案夾或檔案（在不同的層次結構中），所以我們的search演算法可以掃描查詢的所有可能匹配項非常重要。舉個完整的例子，讓我們包含file c3在folder b1 和 folder b4中。搜索此檔案時，我們希望看到兩個路徑都回傳 -

const root =
  new Folder("root folder", [
    new File("file a1"),
    new File("file a2"),
    new Folder("folder a3", [
      new Folder("folder b1", [
        new File("file c1"),
        new File("file c2"),
        new File("file c3")  // ? could have the same name
      ]),
      new File("file b2"),
      new File("file b3"),
      new Folder("folder b4", [
        new File("file c3"), // ? could have the same name
        new File("file c4"),
        new File("file c5")
      ])
    ]),
    new File("file a4")
  ])

演算法

現在我們已經解決了代碼的其他問題，讓我們撰寫search(t, query). 我們可以使用歸納推理來做到這一點-

如果t是 File 并且它name與匹配query，則產生單例結果[t]
（歸納）t不是檔案。Ift是一個 Folder 并且它name與query輸入的單例結果匹配[t]。并且對于所有child的t.children，對于所有path的遞回子問題，在and yieldsearch(child, query)前面加上。tpath
（歸納）t既不是檔案也不是檔案夾。拋出型別錯誤以通知呼叫者。

function* search(t, query) {
  switch(t?.constructor) {
    case File:
      if (t.name == query)
        yield [t]
      break
    case Folder:
      if (t.name == query)
        yield [t]
      for (const child of t.children)
        for (const path of search(child, query))
          yield [t, ...path]
      break
    default:
      throw Error(`cannot search unsupported type ${t}`)
  }
}

以下是一些搜索示例 -

for (const path of search(root, "root folder"))
  console.log([".", ...path.map(f => f.name)].join("/"))

./root folder

for (const path of search(root, "file a1"))
  console.log([".", ...path.map(f => f.name)].join("/"))

./root folder/file a1

多次找到檔案或檔案夾時回傳多個路徑 -

for (const path of search(root, "file c3"))
  console.log([".", ...path.map(f => f.name)].join("/"))

./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3

當找不到檔案或檔案夾時，不給出輸出 -

for (const path of search(root, "file Q"))
  console.log([".", ...path.map(f => f.name)].join("/"))

?? no output

呼叫者決定效果

通過產生一系列物件Folder和File物件，我們的search演算法保持通用性和可重用性。默認情況下不組裝字串，并且不會將任何內容記錄到控制臺。如果呼叫者希望創建一個/-separated 路徑，如上所示。不同效果的選項留給呼叫者決定。

只有一個結果

使用生成器非常適合，search因為呼叫者可以選擇使用所有匹配項或任意數量的匹配項。在此示例中，我們使用泛型first僅回傳第一個匹配項。請注意，在找到匹配項后立即取消生成器，并且 cpu 不做任何額外的作業 -

function first(iter) {
  for (const v of iter)
    return v
}

const match = first(search(root, "file c3"))

if (match)
  console.log("found:", match.map(f => f.name).join("/"))
else
  console.error("no match found")

found: root folderfolder a3/folder b1/file c3

first如果以這種方式使用，請確保進行正確的空值檢查，因為search在找不到匹配項時可能不會產生任何結果 -

const match = first(search(root, "ZZZ"))

if (match)
  console.log("found:", match.map(f => f.name).join("/"))
else
  console.error("no match found")

no match found

高階搜索

在原始演算法中，匹配是使用確定的==。如果我們允許呼叫者指定構成匹配的內容，該演算法可能會更有用 -

function* search(t, query) {
  switch(t?.constructor) {
    case File:
      if (Boolean(query(t.name))) // ? query is a func
        yield [t]
      break
    case Folder:
      if (Boolean(query(t.name))) // ? query is a func
        yield [t]
      for (const child of t.children)
        for (const path of search(child, query))
          yield [t, ...path]
      break
    default:
      throw Error(`cannot search unsupported type ${t}`)
  }
}

file c讓我們找到所有以-開頭的檔案

for (const path of search(root, filename => filename.startsWith("file c")))
  console.log([".", ...path.map(f => f.name)].join("/"))

./root folder/folder a3/folder b1/file c1
./root folder/folder a3/folder b1/file c2
./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3
./root folder/folder a3/folder b4/file c4
./root folder/folder a3/folder b4/file c5

專業化

使用高階search函式，您可以輕松實作searchByString. 這被稱為專業化-

function searchByString(t, query) {
  return search(t, filename => filename == query)
}

for (const path of searchByString(root, "file c3"))
  console.log([".", ...path.map(f => f.name)].join("/"))

./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3

代碼演示

上面的代碼已經被壓縮，所以你可以在一個地方看到它。運行代碼段并驗證輸出 -

class File { constructor(name) { this.name = name } }

class Folder { constructor(name, children) { this.name = name;  this.children = children } }

function* search(t, query) {
  switch(t?.constructor) {
    case File: if (Boolean(query(t.name))) yield [t];  break
    case Folder: if (Boolean(query(t.name))) yield [t]; for (const child of t.children) for (const path of search(child, query)) yield [t, ...path]; break
    default: throw Error(`cannot search unsupported type ${t}`)
  }
}

function searchByString(t, query) {
  return search(t, filename => filename == query)
}

const relative = (path) => [".", ...path.map(f => f.name)].join("/")

const root = new Folder("root folder", [new File("file a1"), new File("file a2"), new Folder("folder a3", [new Folder("folder b1", [new File("file c1"), new File("file c2"), new File("file c3")]), new File("file b2"), new File("file b3"), new Folder("folder b4", [new File("file c3"), new File("file c4"), new File("file c5")])]), new File("file a4")])

console.log("== exact match ==")
for (const path of search(root, filename => filename == "root folder"))
  console.log(relative(path))

console.log("== starts with 'file c' ==")
for (const path of search(root, filename => filename.startsWith("file c")))
  console.log(relative(path))

console.log("== searchByString ==")
for (const path of searchByString(root, "file c3"))
  console.log(relative(path))

.as-console-wrapper { min-height: 100%; top: 0; }

== exact match ==
./root folder
== starts with 'file c' ==
./root folder/folder a3/folder b1/file c1
./root folder/folder a3/folder b1/file c2
./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3
./root folder/folder a3/folder b4/file c4
./root folder/folder a3/folder b4/file c5
== searchByString ==
./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3

Python

search用 Python 寫的完全一樣 -

class file:
  def __init__(self, name):
    self.name = name

class folder:
  def __init__(self, name, children):
    self.name = name
    self.children = children

def search(t, query):
  if isinstance(t, file):
    if t.name == query:
      yield [t]
  elif isinstance(t, folder):
    if t.name == query:
      yield [t]
    for child in t.children:
      for path in search(child, query):
        yield [t, *path]
  else:
    raise TypeError("unsupported", t)

如果您使用的是 Python 3.10，則可以使用一些新功能。調整search以利用新的結構match..case語法 -

from dataclasses import dataclass
from typing import Generator, Union

Ftree = Union["file", "folder"]

@dataclass
class file:
  name: str

@dataclass
class folder:
  name: str
  children: list[Ftree]

def search(t: Ftree, query: str) -> Generator[list[Ftree], None, None]:
  match t:
    case file(name):
      if name == query: yield [t]
    case folder(name, children):
      if name == query: yield [t]
      for child in t.children:
        for path in search(child, query):
          yield [t, *path]
    case _:
      raise TypeError("unsupported", t)

給定一棵樹 -

root = \
  folder("root folder", [
    file("file a1"),
    file("file a2"),
    folder("folder a3", [
      folder("folder b1", [
        file("file c1"),
        file("file c2"),
        file("file c3")
      ]),
      file("file b2"),
      file("file b3"),
      folder("folder b4", [
        file("file c3"),
        file("file c4"),
        file("file c5")
      ])
    ]),
    file("file a4")
  ])

兩種實作的行為相同 -

for path in search(root, "root folder"):
  print("/".join([".", *map(lambda f: f.name, path)]))

./root folder

for path in search(root, "file c3"):
  print("/".join([".", *map(lambda f: f.name, path)]))

./root folder/folder a3/folder b1/file c3
./root folder/folder a3/folder b4/file c3

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/472656.html

標籤：javascript Python 算法递归

上一篇：這是技術問題嗎？數學問題？一個Python問題？

下一篇：GoogleCloudpostgres–從Heroku連接