code: 
  
  
  
  
  
  import json
  import os
  import shutil
  import sys
  import tempfile
  import unittest
  from unittest import TestCase
  from unittest.mock import patch
  
  import faiss
  import numpy as np
  from datasets import Dataset
  
  from transformers import BartConfig, BartTokenizer, DPRConfig, DPRQuestionEncoderTokenizer, RagConfig
  from transformers.file_utils import is_datasets_available, is_faiss_available, is_psutil_available, is_torch_available
  from transformers.integrations import is_ray_available
  from transformers.models.bert.tokenization_bert import VOCAB_FILES_NAMES as DPR_VOCAB_FILES_NAMES
  from transformers.models.rag.retrieval_rag import CustomHFIndex, RagRetriever
  from transformers.models.roberta.tokenization_roberta import VOCAB_FILES_NAMES as BART_VOCAB_FILES_NAMES
  from transformers.testing_utils import require_ray
  
  
  sys.path.append(os.path.join(os.getcwd()))  # noqa: E402 # noqa: E402 # isort:skip
  
  if is_torch_available():
  				from distributed_pytorch_retriever import RagPyTorchDistributedRetriever  # noqa: E402 # isort:skip
  else:
  				__lowerCAmelCase     =			None
  
  if is_ray_available():
  				import ray  # noqa: E402 # isort:skip
  				from distributed_ray_retriever import RagRayDistributedRetriever, RayRetriever  # noqa: E402 # isort:skip
  else:
  				__lowerCAmelCase     =			None
  				__lowerCAmelCase     =			None
  				__lowerCAmelCase     =			None
  
  def     a						(      _lowercase   :     Optional[int]       )     ->Any:
  		if not (is_datasets_available() and is_faiss_available() and is_psutil_available()):
  				UpperCamelCase__         =	unittest.skip("""test requires Datasets, Faiss, psutil"""       )(_lowercase       )
  		return test_case
  
  
  
  
  @require_distributed_retrieval
  class   _UpperCAmelCase	(   _lowercase					):
  
  
  
  
  					def 	snake_case_		(						self       )						->  List[str]:
  							UpperCamelCase__         =	tempfile.mkdtemp()
  							UpperCamelCase__         =	8
  
  							# DPR tok
  							UpperCamelCase__         =	[
  							    """[UNK]""",
  							    """[CLS]""",
  							    """[SEP]""",
  							    """[PAD]""",
  							    """[MASK]""",
  							    """want""",
  							    """##want""",
  							    """##ed""",
  							    """wa""",
  							    """un""",
  							    """runn""",
  							    """##ing""",
  							    """,""",
  							    """low""",
  							    """lowest""",
  							]
  							UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """dpr_tokenizer"""       )
  							os.makedirs(__lowerCAmelCase    ,      exist_ok=__lowerCAmelCase       )
  							UpperCamelCase__         =	os.path.join(__lowerCAmelCase    ,      DPR_VOCAB_FILES_NAMES["""vocab_file"""]       )
  							with open(self.vocab_file    ,      """w"""    ,      encoding="""utf-8"""       ) as vocab_writer:
  									vocab_writer.write("""""".join([x + """\n""" for x in vocab_tokens]       )       )
  
  							# BART tok
  							UpperCamelCase__         =	[
  							    """l""",
  							    """o""",
  							    """w""",
  							    """e""",
  							    """r""",
  							    """s""",
  							    """t""",
  							    """i""",
  							    """d""",
  							    """n""",
  							    """\u0120""",
  							    """\u0120l""",
  							    """\u0120n""",
  							    """\u0120lo""",
  							    """\u0120low""",
  							    """er""",
  							    """\u0120lowest""",
  							    """\u0120newer""",
  							    """\u0120wider""",
  							    """<unk>""",
  							]
  							UpperCamelCase__         =	dict(zip(__lowerCAmelCase    ,      range(len(__lowerCAmelCase       )       )       )       )
  							UpperCamelCase__         =	["""#version: 0.2""", """\u0120 l""", """\u0120l o""", """\u0120lo w""", """e r""", """"""]
  							UpperCamelCase__         =	{"""unk_token""": """<unk>"""}
  
  							UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """bart_tokenizer"""       )
  							os.makedirs(__lowerCAmelCase    ,      exist_ok=__lowerCAmelCase       )
  							UpperCamelCase__         =	os.path.join(__lowerCAmelCase    ,      BART_VOCAB_FILES_NAMES["""vocab_file"""]       )
  							UpperCamelCase__         =	os.path.join(__lowerCAmelCase    ,      BART_VOCAB_FILES_NAMES["""merges_file"""]       )
  							with open(self.vocab_file    ,      """w"""    ,      encoding="""utf-8"""       ) as fp:
  									fp.write(json.dumps(__lowerCAmelCase       ) + """\n"""       )
  							with open(self.merges_file    ,      """w"""    ,      encoding="""utf-8"""       ) as fp:
  									fp.write("""\n""".join(__lowerCAmelCase       )       )
  
  
  
  
  					def 	snake_case_		(						self       )						->  DPRQuestionEncoderTokenizer:
  							return DPRQuestionEncoderTokenizer.from_pretrained(os.path.join(self.tmpdirname    ,      """dpr_tokenizer"""       )       )
  
  
  
  
  					def 	snake_case_		(						self       )						->  BartTokenizer:
  							return BartTokenizer.from_pretrained(os.path.join(self.tmpdirname    ,      """bart_tokenizer"""       )       )
  
  
  
  
  					def 	snake_case_		(						self       )						->  Optional[Any]:
  							shutil.rmtree(self.tmpdirname       )
  
  
  
  
  					def 	snake_case_		(						self       )						->  List[str]:
  							UpperCamelCase__         =	Dataset.from_dict(
  							    {
  							        """id""": ["""0""", """1"""],
  							        """text""": ["""foo""", """bar"""],
  							        """title""": ["""Foo""", """Bar"""],
  							        """embeddings""": [np.ones(self.retrieval_vector_size       ), 2 * np.ones(self.retrieval_vector_size       )],
  							    }       )
  							dataset.add_faiss_index("""embeddings"""    ,      string_factory="""Flat"""    ,      metric_type=faiss.METRIC_INNER_PRODUCT       )
  							return dataset
  
  
  
  
  					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase=12_345       )						->  RagPyTorchDistributedRetriever:
  							UpperCamelCase__         =	self.get_dummy_dataset()
  							UpperCamelCase__         =	RagConfig(
  							    retrieval_vector_size=self.retrieval_vector_size    ,      question_encoder=DPRConfig().to_dict()    ,      generator=BartConfig().to_dict()    ,      )
  							with patch("""transformers.models.rag.retrieval_rag.load_dataset"""       ) as mock_load_dataset:
  									UpperCamelCase__         =	dataset
  									UpperCamelCase__         =	RagPyTorchDistributedRetriever(
  									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      )
  									if init_retrieval:
  											retriever.init_retrieval(__lowerCAmelCase       )
  							return retriever
  
  
  
  
  					def 	snake_case_		(						self    ,      __lowerCAmelCase       )						->  RagRayDistributedRetriever:
  							# Have to run in local mode because sys.path modifications at top of
  							# file are not propogated to remote workers.
  							# https://stackoverflow.com/questions/54338013/parallel-import-a-python-file-from-sibling-folder
  							ray.init(local_mode=__lowerCAmelCase       )
  							UpperCamelCase__         =	RagConfig(
  							    retrieval_vector_size=self.retrieval_vector_size    ,      question_encoder=DPRConfig().to_dict()    ,      generator=BartConfig().to_dict()    ,      )
  							UpperCamelCase__         =	ray.remote(__lowerCAmelCase       )
  							UpperCamelCase__         =	[remote_cls.remote() for _ in range(1       )]
  							with patch("""transformers.models.rag.retrieval_rag.load_dataset"""       ) as mock_load_dataset:
  									UpperCamelCase__         =	self.get_dummy_dataset()
  									UpperCamelCase__         =	RagRayDistributedRetriever(
  									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      retrieval_workers=__lowerCAmelCase    ,      )
  									if init_retrieval:
  											retriever.init_retrieval()
  							return retriever
  
  
  
  
  					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase=12_345       )						->  List[Any]:
  							UpperCamelCase__         =	self.get_dummy_dataset()
  							UpperCamelCase__         =	RagConfig(
  							    retrieval_vector_size=self.retrieval_vector_size    ,      question_encoder=DPRConfig().to_dict()    ,      generator=BartConfig().to_dict()    ,      index_name="""custom"""    ,      )
  							if from_disk:
  									UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """dataset"""       )
  									UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """index.faiss"""       )
  									dataset.get_index("""embeddings"""       ).save(os.path.join(self.tmpdirname    ,      """index.faiss"""       )       )
  									dataset.drop_index("""embeddings"""       )
  									dataset.save_to_disk(os.path.join(self.tmpdirname    ,      """dataset"""       )       )
  									del dataset
  									UpperCamelCase__         =	RagPyTorchDistributedRetriever(
  									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      )
  							else:
  									UpperCamelCase__         =	RagPyTorchDistributedRetriever(
  									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      index=CustomHFIndex(config.retrieval_vector_size    ,      __lowerCAmelCase       )    ,      )
  							if init_retrieval:
  									retriever.init_retrieval(__lowerCAmelCase       )
  							return retriever
  
  
  
  
  					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )						->  List[Any]:
  							# Have to run in local mode because sys.path modifications at top of
  							# file are not propogated to remote workers.
  							# https://stackoverflow.com/questions/54338013/parallel-import-a-python-file-from-sibling-folder
  							ray.init(local_mode=__lowerCAmelCase       )
  							UpperCamelCase__         =	self.get_dummy_dataset()
  							UpperCamelCase__         =	RagConfig(
  							    retrieval_vector_size=self.retrieval_vector_size    ,      question_encoder=DPRConfig().to_dict()    ,      generator=BartConfig().to_dict()    ,      index_name="""custom"""    ,      )
  							UpperCamelCase__         =	ray.remote(__lowerCAmelCase       )
  							UpperCamelCase__         =	[remote_cls.remote() for _ in range(1       )]
  							if from_disk:
  									UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """dataset"""       )
  									UpperCamelCase__         =	os.path.join(self.tmpdirname    ,      """index.faiss"""       )
  									dataset.get_index("""embeddings"""       ).save(os.path.join(self.tmpdirname    ,      """index.faiss"""       )       )
  									dataset.drop_index("""embeddings"""       )
  									dataset.save_to_disk(os.path.join(self.tmpdirname    ,      """dataset"""       )       )
  									del dataset
  									UpperCamelCase__         =	RagRayDistributedRetriever(
  									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      retrieval_workers=__lowerCAmelCase    ,      index=CustomHFIndex.load_from_disk(
  									        vector_size=config.retrieval_vector_size    ,      dataset_path=config.passages_path    ,      index_path=config.index_path    ,      )    ,      )
  							else:
  									UpperCamelCase__         =	RagRayDistributedRetriever(
  									    __lowerCAmelCase    ,      question_encoder_tokenizer=self.get_dpr_tokenizer()    ,      generator_tokenizer=self.get_bart_tokenizer()    ,      retrieval_workers=__lowerCAmelCase    ,      index=CustomHFIndex(config.retrieval_vector_size    ,      __lowerCAmelCase       )    ,      )
  							if init_retrieval:
  									retriever.init_retrieval()
  							return retriever
  
  
  
  
  					def 	snake_case_		(						self    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )						->  None:
  							UpperCamelCase__  ,			UpperCamelCase__  ,			UpperCamelCase__         =	retriever.retrieve(__lowerCAmelCase    ,      n_docs=__lowerCAmelCase       )
  							self.assertEqual(retrieved_doc_embeds.shape    ,      (2, n_docs, self.retrieval_vector_size)       )
  							self.assertEqual(len(__lowerCAmelCase       )    ,      2       )
  							self.assertEqual(sorted(doc_dicts[0]       )    ,      ["""embeddings""", """id""", """text""", """title"""]       )
  							self.assertEqual(len(doc_dicts[0]["""id"""]       )    ,      __lowerCAmelCase       )
  							self.assertEqual(doc_dicts[0]["""id"""][0]    ,      """1"""       )  # max inner product is reached with second doc
  							self.assertEqual(doc_dicts[1]["""id"""][0]    ,      """0"""       )  # max inner product is reached with first doc
  							self.assertListEqual(doc_ids.tolist()    ,      [[1], [0]]       )
  
  
  
  
  					def 	snake_case_		(						self       )						->  str:
  							UpperCamelCase__         =	1
  							UpperCamelCase__         =	np.array(
  							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )
  
  							self.distributed_retriever_check(
  							    self.get_dummy_pytorch_distributed_retriever(init_retrieval=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )
  
  
  
  
  					def 	snake_case_		(						self       )						->  int:
  							UpperCamelCase__         =	1
  							UpperCamelCase__         =	np.array(
  							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )
  
  							self.distributed_retriever_check(
  							    self.get_dummy_custom_hf_index_pytorch_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      )
  
  
  
  
  					def 	snake_case_		(						self       )						->  Union[str, Any]:
  							UpperCamelCase__         =	1
  							UpperCamelCase__         =	np.array(
  							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )
  
  							self.distributed_retriever_check(
  							    self.get_dummy_custom_hf_index_pytorch_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      )
  
  
  
  
  					@require_ray
  					def 	snake_case_		(						self       )						->  str:
  							UpperCamelCase__         =	1
  							UpperCamelCase__         =	np.array(
  							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )
  
  							self.distributed_retriever_check(
  							    self.get_dummy_ray_distributed_retriever(init_retrieval=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )
  							ray.shutdown()
  
  
  
  
  					@require_ray
  					def 	snake_case_		(						self       )						->  List[Any]:
  							UpperCamelCase__         =	1
  							UpperCamelCase__         =	np.array(
  							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )
  							with self.assertRaises(__lowerCAmelCase       ):
  									self.distributed_retriever_check(
  									    self.get_dummy_custom_hf_index_ray_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase    ,      )
  							ray.shutdown()
  
  
  
  
  					@require_ray
  					def 	snake_case_		(						self       )						->  Union[str, Any]:
  							UpperCamelCase__         =	1
  							UpperCamelCase__         =	np.array(
  							    [np.ones(self.retrieval_vector_size       ), -np.ones(self.retrieval_vector_size       )]    ,      dtype=np.floataa       )
  
  							self.distributed_retriever_check(
  							    self.get_dummy_custom_hf_index_ray_retriever(init_retrieval=__lowerCAmelCase    ,      from_disk=__lowerCAmelCase       )    ,      __lowerCAmelCase    ,      __lowerCAmelCase       )
  							ray.shutdown()
  
  
  
  
  
  
style_context: 
  
  
  
  
  
  def     a						(      _lowercase   :     List[str]       )     ->List[str]:
  		UpperCamelCase__         =	[7_0_1, 3_0_1, 1_3_2, 5_7, 2_3, 1_0, 4, 1]
  		for gap in gaps:
  				for i in range(_lowercase ,						len(_lowercase       )       ):
  						UpperCamelCase__         =	collection[i]
  						UpperCamelCase__         =	i
  						while j >= gap and collection[j - gap] > insert_value:
  								UpperCamelCase__         =	collection[j - gap]
  								j -= gap
  						if j != i:
  								UpperCamelCase__         =	insert_value
  		return collection
  
  
  if __name__ == "__main__":
  				from doctest import testmod
  
  				testmod()
  				__lowerCAmelCase     =			input("Enter numbers separated by a comma:\n").strip()
  				__lowerCAmelCase     =			[int(item) for item in user_input.split(",")]
  				print(shell_sort(unsorted))
  
  
  
  
  
  